Merge Sort algorithm

Merge Sort is one of the most efficient, Divide and Conquer sorting algorithms having an O(n log n) time complexity in all cases. In most implementations Merge Sort produce a stable sort, which means that the order of equal elements is the same in the input and output.

Merge Sort algorithm


1) Divide

In Merge Sort, the given unsorted array of elements is divided into sub-arrays recursively, recursion stops when there is only a single element in any input array, because a single element is always sorted in itself.

The array is divided into a possible half, each part of the array is copied to two new sub-arrays of length (0 to mid-1) and (mid to n), these arrays are further divided in recursive manner until there is only one element left.

[7, 2, 1, 6, 2, 5, 3, 4]

[7, 2, 1, 6]	[2, 5, 3, 4]

[7, 2]	[1, 6]	[2, 5]	[3, 4]

[7]	[2]	[1]	[6]	[2]	[5]	[3]	[4]

2) Merge

Divided sub arrays are merged in recursive and sorted order, elements from both list are compared and we put smaller element to the merged array, if any of the sub-array is exhausted first the remaining elements are simply copied.

[7]	[2]	[1]	[6]	[2]	[5]	[3]	[4]

[2,7]	[1,6]	[2,5]	[3,4]

[1,2,6,7]	[2,3,4,5]

[1,2,2,3,4,5,6,7]
Merge Sort have a space complexity of O(n), requiring equal amount of additional space as the unsorted array. Hence its not at all recommended for searching large unsorted arrays.


Merge Sort Implementation in Java

Here is the code for Merge Sort Implementation in Java, we have created a method mergeSort(), it takes an array of element to be sorted, if the array have only one element recursion ends. A possible mid point divided input array into two sub arrays, these sub arrays are further called for mergeSort(int[] arr) and than merged in sorted order.

Another method merge() is where actual sorting happens, first if both arrays have elements we pick smaller element to put in merged array, if one arrays is exhausted another arrays is simply copied.
package com.tb.arrays.sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class MergeSort {

	static int[] input = { 7, 2, 1, 6, 2, 5, 3, 4 };

	private static void mergeSort(int[] arr) {

		int n = arr.length;

		if (n < 2)
			return;

		int mid = n / 2;
		int lArr[] = new int[mid];
		int rArr[] = new int[n - mid];

		for (int i = 0; i < mid; i++)
			lArr[i] = arr[i];
		for (int i = mid; i < n; i++)
			rArr[i - mid] = arr[i];

		mergeSort(lArr);
		mergeSort(rArr);

		merge(lArr, rArr, arr);

	}

	private static void merge(int[] leftArray, int[] rightArray, int[] arr) {

		int i = 0, j = 0, k = 0;
		int nLeft = leftArray.length;
		int nRight = rightArray.length;

		while (i < nLeft && j < nRight) {
			if (leftArray[i] < rightArray[j]) {
				arr[k] = leftArray[i];
				i++;
			} else {
				arr[k] = rightArray[j];
				j++;
			}
			k++;
		}

		while (i < nLeft) {
			arr[k] = leftArray[i];
			i++;
			k++;
		}

		while (j < nRight) {
			arr[k] = rightArray[j];
			j++;
			k++;
		}
	}

	private static String printArrays(int[] input) {
		return Arrays.stream(input).mapToObj(String::valueOf).collect(Collectors.joining(", "));

	}

	public static void main(String[] args) {
		System.out.println("Array before sort: " + printArrays(input));
		mergeSort(input);
		System.out.println("Array after sort: " + printArrays(input));
	}

}
Output: Output of above code will be something like this.

Array before sort: 7, 2, 1, 6, 2, 5, 3, 4
Array after sort: 1, 2, 2, 3, 4, 5, 6, 7
In this article we have seen "What is Merge sort?", Merge sort time complexity, usage and how to implement Merge sort algorithm in Java.