Merge Sort

Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.

To sort A[p .. r]:

• Divide StepIf a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p .. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].
• Conquer StepConquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].
• Combine StepCombine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).

Note that the recursion bottoms out when the subarray has just one element, so that it is trivially sorted.

For example,

Linear Time Merge
As the left and right partitions are sorted so we can merge in linear time by using two pointers to scan the partitions left to right such that we take the small element from elements currently pointed by the pointers and progress that pointer to right.

Worst case time complexity O(n log n) and space complexity is O(n).

public class Mergesort {
  private int[] numbers;
  private int[] helper;

  private int number;

  public void sort(int[] values) {
    this.numbers = values;
    number = values.length;
    this.helper = new int[number];
    mergesort(0, number - 1);
  }

  private void mergesort(int low, int high) {
    // check if low is smaller then high, if not then the array is sorted
    if (low < high) {
      // Get the index of the element which is in the middle
      int middle = low + (high - low) / 2;
      // Sort the left side of the array
      mergesort(low, middle);
      // Sort the right side of the array
      mergesort(middle + 1, high);
      // Combine them both
      merge(low, middle, high);
    }
  }

  private void merge(int low, int middle, int high) {

    // Copy both parts into the helper array
    for (int i = low; i <= high; i++) {
      helper[i] = numbers[i];
    }

    int i = low;
    int j = middle + 1;
    int k = low;
    // Copy the smallest values from either the left or the right side back
    // to the original array
    while (i <= middle && j <= high) {
      if (helper[i] <= helper[j]) {
        numbers[k] = helper[i];
        i++;
      } else {
        numbers[k] = helper[j];
        j++;
      }
      k++;
    }
    // Copy the rest of the left side of the array into the target array
    while (i <= middle) {
      numbers[k] = helper[i];
      k++;
      i++;
    }

  }
} 

In Place Merge Sort
The slightly tricky part is the merge logic. As usual, we have a pointer into the left partition (x[left]) and the right partiton (x[right]). If x[left] is less than or equal to x[right], then it is already in place within the sorted merged array, so just increment left. Otherwise, the array element in x[right] needs to move down into the space currently occupied by x[left], and to accommodate this, the entire array segment from x[left] through x[right-1] needs to move up by one — effectively we need to rotate that little segment of the array. In the process, everything moves up by one, including the end of the left segment (mid).

public static void rotateRight(int[] A, int i, int j){
	int temp = A[j];
	System.arraycopy(A, i, A, i+1, j-i);
	A[i] = temp;
}

public static void mergeInPlace(int[] A, int i, int j){
	while(i < j && i < A.length && j < A.length){
		if(A[i] > A[j]){
			rotateRight(A, i, j);
			i++;
			j++;
		}
		else{
			i++;
		}
	}
}

public static void mergeSortInPlace(int[] A, int i, int j){
	if(i >= j){
		return;
	}
	int k  = (i+j)/2;
	
	mergeSortInPlace(A, i, k);
	mergeSortInPlace(A, k+1, j);
	mergeInPlace(A, i, k+1);
}

On average case the merge process using the rotation is O(n). However, this case has markedly different best- and worst-case situations. The code explicitly notes the very best case (if the end of the left half is in position with respect to the beginning of the right half, return), but even just shy of the best case (say, one item out of position), the data movement will still be O(1). That means that the complexity will be O(n). For lg(n) levels, we have 1+2+4+8+ . . . (i.e., the number of method invocations at each level of the recursive execution tree).

In the worst case, however, within each execution the entire right side needs to be moved to the left side — require O(n^2) data movements (thanks to the well-known series “1+2+3+4+5+…”). Even in the average case, one can expect half the time to need to move from the right side, again giving O(n2) data movements.

Merge Sort of Linked Lists
The idea is same. Repeatedly halve the list and then merge. In order to splitting the array into two halves we can use the sam technique described in my previous post. Basically we can use slow and fast pointer to split the list into two halves repeatedly. Then merging process is quite straightforward and we just have to manipulate couple of linked list pointers.

public static ListNode mergeSortedLists(ListNode a, ListNode b){
	if(a == null){
		return b;
	}
	if(b == null){
		return a;
	}
	
	ListNode merged = null;
	
	if(a.val > b.val){
		merged = b;
		merged.next = mergeSortedLists(a, b.next);
	}
	else{
		merged = a;
		merged.next = mergeSortedLists(a.next, b);
	}
	
	return merged;
}

public static void MergeSortList(ListNode head){
	if(head != null && head.next != null){
		ListNode left = head;
		ListNode right = splitLinkedListNode2(left, 2);
		MergeSortList(left);
		MergeSortList(right);
		
		head = mergeSortedLists(left, right);
	}
}

public static ListNode splitLinkedListNode2(ListNode head, int n){
	ListNode slow = head;
	ListNode fast = head;
	ListNode prev = head;
	
	while(fast != null && slow != null){
		int count = 0;
		prev = slow;
		slow=slow.next;
		while(count < n && fast != null){
			fast = fast.next;
			count++;
		}
		
		if(slow == fast){
			return null;
		}
	}
	
	if(prev != null){
		prev.next = null;
	}
	
	return slow;
}