List three advanced sorting algorithms,

Merge sort, Heap sort and Quick sort. with java implementations.

Stability of the algorithm means :

before sorting:

if (a[i1] == a[j1] && i1 < j1)

after sorting:

i2 < j2

Merge Sort

• The idea of merger sort is Divide and Conque, which is to split the array into two halfs, sort them separately and merge them into one,
• it needs an addtional space(array) to store the temp result,
• Time complexity is straigtly O(N lg N),
• Stable: Yes, cause the logic only swaps adjacent elements

	public static void mergeSort( int [] a, int lo, int hi) {
		if (hi <= lo) {
			return;
		}
		int mid = (lo + hi) >>> 1;
		mergeSort(a, lo, mid);
		mergeSort(a, mid + 1, hi);
		merge(a, lo, mid, hi);
	}

	public static void merge(int[] a, int lo, int mid, int hi) {
		int i = lo, j = mid + 1;  // i: low index, j: high index
		for (int k = lo; k <= hi; k++) {
			aux[k] = a[k];
		}
		for (int k = lo; k <= hi; k++) { // k: merged index
			if (i > mid) {  // low half finished
				a[k] = aux[j++];
			} else if (j > hi) { // high half finished
				a[k] = aux[i++];
			} else if (aux[j] <  (aux[i]) ) { // low/high are not finish
				a[k] = aux[j++];
			} else {
				a[k] = aux[i++];
			}
		}
	}

Heap Sort

• The idea of Heap sort is to use the characteristic of heap, build a Big-Top heap, and move the root(biggest) to the tail and keep doing this.
• does not need additional space,
• Time complexity is straigtly O(N lg N),
• Stalbe: No, cause there is parent-child swapping, which doesn't keep the order.

	public static void heapSort(int arr[])  {
		int n = arr.length;
		// Build max heap, from all non-leaf nodes (n/2 -> 0), Max at the top
		for (int i = n / 2 - 1; i >= 0; i--) {
			heapify(arr, n, i);
		}
		// Heap sort
		for (int i=n-1; i>=0; i--)  {
			// swap the first (max), and last
			int temp = arr[0];
			arr[0] = arr[i];
			arr[i] = temp;
			// Heapify root element
			heapify(arr, i, 0);
		}
	}

	public static void heapify(int arr[], int n, int i)  {
		// Find largest among root, left child and right child
		int largest = i; 
		int l = 2*i + 1; 
		int r = 2*i + 2;  

		if (l < n && arr[l] > arr[largest])
			largest = l;

		if (r < n && arr[r] > arr[largest])
			largest = r;

		// Swap if require and continue heapifying if swap
		if (largest != i)  {
			int swap = arr[i];
			arr[i] = arr[largest];
			arr[largest] = swap;
			// heapify the effect child node
			heapify(arr, n, largest);
		}
	}

Quick Sort

• The idea of quick sort is also Divide and Conque, which is similiar to Merge sort,
• It picks an element (called pivot) and puts it into the correct position (All smaller elements are in front of it and greater elements are after it.)
• Repeat the same process for the two sections in front and after the pivot),
• There is several way to pick the pivot, which could be the first element, last element or a random element in the array.
• For normal case, Time complexity is O(N lg N), for the worst case( array already sorted and pick the first as pivot, this does not acutally split the array) time complexity is O(N^2)
• Stalbe: suppose to yse,

	public static void quickSort(int[] a){
		quickSort(a, 0, a.length-1);
	}
	private static void quickSort(int[] a, int low, int high){
		if (low < high){
			int pivot = partition(a, low, high);        // divide
			quickSort(a, low, pivot-1);                   // recursively process low part
			quickSort(a, pivot+1, high);                  // recursively process high part
		}
	}
	private static int partition(int[] a, int low, int high){
		int pivot = a[low];     // use the fist as pivot
		while (low < high){
			while (low < high && a[high] >= pivot) --high; 
			a[low]=a[high];             //  
			while (low < high && a[low] <= pivot) ++low;
			a[high] = a[low];           //swap
		}
		a[low] = pivot; // low/high is the right position of pivot
		return low;// index of pivot
	}