merge sort

Work in Progress

Summary

Merge sort

  • comparison based
  • divide-and-conquer
  • not in-place (requires extra space)
  • stable
  • recursive

Time complexity

  • splits array in half each recursion -> depth
  • merging each level takes
  • all cases: - array is always split in half

Blackbox sorting

Concept

Algorithm

  1. if array has 0 or 1 element, it is sorted
  2. divide array into two halves
  3. recursively sort each half
  4. merge the two sorted halves
java
private static void mergeSort(int a[], int low, int high) {
	// the array to be sorted is a[low..high]
	if (low < high) { // base case: low >= high (0 or 1 item)
		int mid = (low + high) / 2; 
		mergeSort(a, low, mid); // sort the first half O(n/2 log n/2)
		mergeSort(a, mid + 1, high); // sort the second half
		merge(a, low, mid, high); // conquer: the merge routine O(n)
	}
}

recursive split + merge, handling odd number of elements: larger “half” on the left

Merge subroutine

  • joining two already sorted arrays
  • choose smallest between the two arrays
java
private static void merge(int a[], int low, int mid, int high) {
	// subarray1 = a[low..mid], subarray2 = a[mid+1..high], both sorted
	int N = high-low+1;
	int[] b = new int[N]; // temporary array O(n) space
	int left = low, right = mid+1, bIdx = 0;
	while (left <= mid && right <= high) // the merging
		b[bIdx++] = (a[left] <= a[right]) ? a[left++] : a[right++];
	while (left <= mid) b[bIdx++] = a[left++]; // leftover, if any
	while (right <= high) b[bIdx++] = a[right++]; // leftover, if any
	for (int k = 0; k < N; ++k) a[low+k] = b[k]; // copy back
}

Divide and conquer paradigm

  • breakdown the problem into smaller subproblems
  • divide until the subproblem is trivial

Application

Kattis: classfieldtrip

  • merge two sorted strings
java
Scanner sc = new Scanner(System.in);

// get the two strings
String a = sc.nextLine();
String b = sc.nextLine();

String out = "";

boolean finished = false;

while (a.length() != 0 && b.length() != 0) {
	// compare the first elements of both strings
	if (a.charAt(0) < b.charAt(0)) { // if a[0] < b[0]
		out += a.charAt(0); // merge a[0] into our sorted array
		a = a.substring(1); // remove
	} else {
		out += b.charAt(0);
		b = b.substring(1);
	}
}

// one string might be longer, so add all the leftovers
out += a;
out += b;

System.out.println(out);

can also be done using two pointers, one for each string, to reduce the overhead of string slicing