# SORTING using MergeSore and QuickSort

A quick word about sorting using comparisons, each array with n items has n! permutations, if we look at the algorithm as a binary tree that each node to leaf is a premutation then the are n! node to leaf routes since each binary tree leaf routes is no more than 2^h where h is the height.

than 2^h > n! , and h > log n! , log n! is = n*logn.

MergeSort algorithm:

the algorithm takes nlogn since the recursive call to mergesort will be applied log n times since we can only divide the length of the array log n times. (log base 2).

in each call to mergeSort there will be a call to merge, merge is comparing the subArrays,

the longest comparison will take n/2 compares, since it will compare 2 sub-arrays of the original array, so total run time is n/2*logn which is nlogn.

`public int[] mergesort(int[] arr) {    int[] helper = new int[arr.length];    mergesort(arr, helper, 0, arr.length - 1);    return arr;}public void mergesort(int[] arr, int[] helper, int left, int right) {    if (left < right) {        int middle = (left + right) / 2;        mergesort(arr, helper, left, middle);        mergesort(arr, helper, middle + 1, right);        merge(arr, helper, left, middle, right);    }}public void merge(int[] array, int[] helper, int low, int middle, int high) {    for (int i = low; i <= high; i++) {        helper[i] = array[i];    }    int helperLeft = low;    int helperRight = middle + 1;    int current = low;    while (helperLeft <= middle && helperRight <= high) {        if (helper[helperLeft] <= helper[helperRight]) {            array[current] = helper[helperLeft];            helperLeft++;        } else {            array[current] = helper[helperRight];            helperRight++;        }        current++;    }    int remaining = middle - helperLeft;    for (int i = 0; i <= remaining; i++) {        array[current + i] = helper[helperLeft + i];    }}`

QuickSort algorithm:

`public int[] QuickSort(int[] arr, int left, int right) {    int index = partition(arr, left, right);    if (left < index - 1)        QuickSort(arr, left, index - 1);    if (index < right) {        QuickSort(arr, index, right);    }    return arr;}public int partition(int[] arr, int left, int right) {    int pivot = arr[(left + right) / 2];    while (left <= right) {        while (arr[left] < pivot) left++;        while (arr[right] > pivot) right--;        if (left <= right) {            swap(arr, left, right);            left++;            right--;        }    }    return left;}public void swap(int[] arr, int left, int right) {    int temp = arr[left];    arr[left] = arr[right];    arr[right] = temp;}`