Basic Mergesort

0-basic-mergesort.md

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Basic Mergesort

####Concept

• halve array, creating 2 sub-arrays

• sort each sub array

• merge the sub arrays back together

• this algorithm is recursive

  • to sort: half arrays, and sort sub-arrays
  • each sort halves the arrays until you are left with only 2 elements
    • these elements are then merged together into the first sorted sub array
  • from here, the algorithm steps back up through the recursion, merging arrays

####Implementation

Two main functions need to be written: merge and sort.

---

Merge combines two sorted sub-arrays into a single, sorted array

• create auxiliary array, in which you copy the elements to be merged
• have 3 pointers:
  • i - keeps track of the items in the first sub-array
  • j - keeps track of the items in the second sub-array
  • k - keeps track of position in the final, sorted array
• iterate through the positions of the final array (k)
• for each position, compare elements of first and second sub-arrays at i and j, respectively
  • if element at i is smaller than element at j, place element at i into final array at k
  • increment i

1. Copy

original array [9] [2] [5] [4] [6] [3] [7]
aux array      [9] [2] [5] [4] [6] [3] [7]

2. Divide

original array [3] [2] [4] [6] [1] [7] [8]
                k
aux array      [3] [2] [4] [6] | [1] [7] [8]
                i                 j

3. Compare

aux[i] = 3, aux[j] = 1
aux[j] is smaller
place aux[j] into orig[k]
increment j
increment k

original array [1] [2] [4] [6] [1] [7] [8]
                    k
aux array      [3] [2] [4] [6] | [1] [7] [8]
                i                     j

4. Compare Again

Until k reaches the end of the original array.

---

Sort does the recursion.

• divide the array into two
• calls sort on the two sub-arrays (recursion)
• merge the sorted sub-arrays

####Analysis Mergesort takes time ~N log(N).

• for each recursion, we will need N compares in the merging operation.
  • even if we half, we then have 2 N/2 compares - still sums to N total compares
• the maximum amount of recursions is equal to the amount of times we can divide the arrays by 2: logN times

Mergesort can only sort data as large as half the memory (other half is needed for the aux array).

####Minor Improvements

• for small sub-arrays, use Insertion-sort, as recursion is relatively costly in terms of access time and memory for small arrays.
  • insertion sort is non-recursive
  • insertion sort is ~ linear for small arrays
• check if sorted sub-arrays are already pre-sorted
  • check if last element of sub-array 1 is smaller than first element of sub-array 2

####See Also

• Bottom-Up Mergesort

Merge.java

public class Merge{
	private static Comparable[] aux;
	
	public static void sort(Comparable[] a)
	{
		/* 
		 * aux must be created here. not in the recursion.
		 * we will have many different auxes and use up a lot of memory and time
		 * in array creation.
		 */
		aux = new Comparable[a.length];
		sort(a, aux, 0, a.length - 1);
	}

	public static void sort(Comparable[] a, Comparable aux[], int lo, int hi)
	{
		if (hi <= lo) return;
		int mid = (lo + hi)/2;
		sort (a, aux, lo, mid);
		sort (a, aux, mid + 1, hi);
		merge (a, aux, lo, mid, hi);
	}

	public static void merge(Comparable[] a, Comparable aux[], int lo, int mid, int hi)
	{
		assert isSorted(a, lo, mid);
		assert isSorted(a, mid + 1, hi);

		for (int k = lo; k <= hi; k++)
			aux[k] = a[k];

		int i = lo;
		int j = mid + 1;

		for (int k = lo; k <= hi; k++){
			if 		(i > mid)				a[k] = aux[j++];
			else if (j > hi)				a[k] = aux[i++];
			else if (less(aux[j], aux[i]))	a[k] = aux[j++];
			else 							a[k] = aux[i++];
		}

		assert isSorted(a, lo, hi);
	}
		
	// private
	public static void main(String[] args)
	{
		Integer[] array = {0,2,3,5,1,4,6,7};

		for (Integer i : array)
			System.out.print(i + " ");
		System.out.println();

		Merge.sort(array);

		for (Integer i : array)
			System.out.print(i + " ");
	}

	private static boolean less(Comparable a, Comparable b) { return a.compareTo(b) < 0; }

	private static boolean isSorted(Comparable[] a, int lo, int hi)
	{
		for (int i = lo + 1; i < hi; i++)
			if (less(a[i], a[i-1])) return false;
		return true;
	}
}

MergePrac.java

public class MergePrac{
	private static Comparable[] aux;
	
	public static void sort(Comparable[] a)
	{
		/* 
		 * aux must be created here. not in the recursion.
		 * we will have many different auxes and use up a lot of memory and time
		 * in array creation.
		 */
		aux = new Comparable[a.length];
		sort(a, aux, 0, a.length - 1);
	}

	public static void sort(Comparable[] a, Comparable aux[], int lo, int hi)
	{
		if (hi <= lo) return;
		int mid = (lo + hi)/2;
		int cutoff = 7;

		// if subarrays are small, sort using insertion-sort
		if ((mid - lo) < cutoff) Insert.sort (a, lo, mid);
		else sort (a, aux, lo, mid);

		if ((hi - mid) < cutoff) Insert.sort (a, mid + 1, hi);
		else sort (a, aux, mid + 1, hi);

		// if last of first array < first of second array,
		// arrays are already sorted
		if (less(a[mid], a[mid + 1])) return;

		merge (a, aux, lo, mid, hi);
	}

	public static void merge(Comparable[] a, Comparable aux[], int lo, int mid, int hi)
	{
		assert isSorted(a, lo, mid);
		assert isSorted(a, mid + 1, hi);

		for (int k = lo; k <= hi; k++)
			aux[k] = a[k];

		int i = lo;
		int j = mid + 1;

		for (int k = lo; k <= hi; k++){
			if	(i > mid)		a[k] = aux[j++];
			else if	(j > hi)		a[k] = aux[i++];
			else if	(less(aux[j], aux[i]))	a[k] = aux[j++];
			else				a[k] = aux[i++];
		}

		assert isSorted(a, lo, hi);
	}
		
	// private
	public static void main(String[] args)
	{
		int N = Integer.parseInt(args[0]);
		Integer[] array = new Integer[N];

		for (int i = 0; i < N; i++){
			array[i] = (int)(Math.random() * 100);
			System.out.print(array[i] + " ");
		}
		System.out.println();

		MergePrac.sort(array);

		for (Integer i : array)
			System.out.print(i + " ");
	}

	private static boolean less(Comparable a, Comparable b) { return a.compareTo(b) < 0; }

	private static boolean isSorted(Comparable[] a, int lo, int hi)
	{
		for (int i = lo + 1; i < hi; i++)
			if (less(a[i], a[i-1])) return false;
		return true;
	}
}