In this tutorial, we are going to learn about merge sort in detail and its algorithmic implementation.

Merge Sort

• Divide and Conquer algorithm.
• Recursive in structure.
• Divide the problem into sub-problems that are similar to the original but smaller in size.
• Conquer the sub-problems by solving them recursively. If they are small enough, just solve them in a straight forward manner.
• Combine the solutions to create a solution to the original problem.

Merge Sort Algorithm

Merge-Sort (A, p, r)
INPUT: a sequence of n numbers stored in array A.
OUTPUT: an ordered sequence of n numbers.
MergeSort (A, p, r) // sort A[p..r] by divide & conquer.

1. if p < r
2. then q<-[(p+r)/2]
3. MergeSort (A, p, q)
4. MergeSort (A, q+1, r)
5. Merge (A, p, q, r) // merges A[p..q] with A[q+1..r].

Merge Sort Example

• Sorting Problem: Sort a sequence of n elements into non-decreasing order.
• Divide: Divide the n-element sequence to be sorted into two subsequences of n/2 elements each
• Conquer: Sort the two subsequences recursively using merge sort.
• Combine: Merge the two sorted subsequences to produce the sorted answer.

Insertion Sort Programmatic Implementation in Java

public class MergeSort {

	public static void main(String[] args) {
		int[] intArray = { 20, 35, -15, 7, 55, 1, -22 };
		mergeSort(intArray, 0, intArray.length);
		for (int i = 0; i < intArray.length; i++) {
			System.out.print(intArray[i]+ " ");
		}}
	// { 20, 35, -15, 7, 55, 1, -22 }
	public static void mergeSort(int[] input, int start, int end) {
		if (end - start < 2) {
			return;
		}
		int mid = (start + end) / 2;
		mergeSort(input, start, mid);
		mergeSort(input, mid, end);
		merge(input, start, mid, end);
	}
	// { 20, 35, -15, 7, 55, 1, -22 }
	public static void merge(int[] input, int start, int mid, int end) {
		if (input[mid - 1] <= input[mid]) {
			return;
		}
		int i = start;
		int j = mid;
		int tempIndex = 0;
		int[] temp = new int[end - start];
		while (i < mid && j < end) {
			temp[tempIndex++] = input[i] <= input[j] ? input[i++] : input[j++];
		}
		System.arraycopy(input, i, input, start + tempIndex, mid - i);
		System.arraycopy(temp, 0, input, start, tempIndex);
	}}

Output:

-22 -15 1 7 20 35 55 

Analysis of Merge Sort

• Running time T(n) of Merge Sort:

  • Divide: computing the middle takes O(1)
  • Conquer: solving 2 sub problems takes 2T(n/2)
  • Combine: merging n elements takes O(n)
  • Total: T(n) = O(1) if n = 1.
    T(n) = 2T(n/2) + O(n) if n > 1.
    => T(n) = O(n log n).