# 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;

}