Merge Sort

Merge Sort is a Divide and Conquer algorithm. How this works is, it first divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

The Idea is :

The mergeSort method should recursively sort the subarray array[l..r] i.e. after calling mergeSort(array,l,r) the elements from index l to index r of array should be sorted in ascending order.

Time complexity :

Time complexity of Merge Sort is O(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array into two halves and take linear time to merge two halves.

MergeSort Code :

class MergeSort {
	
	// Main method
	public static void main(String args[]) {
		int arr[] = { 11, 10, 12, 4, 6, 5 };

		System.out.println("Given Unsorted Array :");
		printArray(arr);

		MergeSort ob = new MergeSort();
		ob.mergeSort(arr, 0, arr.length - 1);

		System.out.println("\nSorted array :");
		printArray(arr);
	}

	// The method that sorts arr[l..r] using merge()
	void mergeSort(int arr[], int l, int r) {
		if (l < r) {
			// Find the middle point
			int m = (l + r) / 2;

			// Sort first and second halves
			mergeSort(arr, l, m);
			mergeSort(arr, m + 1, r);

			// Merge the sorted halves
			merge(arr, l, m, r);
		}
	}

	/*
	 * Merges two subarrays of arr[]. First subarray is arr[left..mid] Second
	 * subarray is arr[mid+1..right]
	 */
	void merge(int arr[], int l, int m, int r) {
		// Find sizes of two subarrays to be merged
		int size1 = m - l + 1;
		int size2 = r - m;

		/* Create temp arrays */
		int Left[] = new int[size1];
		int Right[] = new int[size2];

		/* Copy data to temp arrays */
		for (int i = 0; i < size1; ++i)
			Left[i] = arr[l + i];
		for (int j = 0; j < size2; ++j)
			Right[j] = arr[m + 1 + j];

		/* Merge the temp arrays */

		// Initial indexes of first and second subarrays
		int i = 0, j = 0;

		// Initial index of merged subarray array
		int k = l;

		while (i < size1 && j < size2) {
			if (Left[i] <= Right[j]) {
				arr[k] = Left[i];
				i++;
			} else {
				arr[k] = Right[j];
				j++;
			}
			k++;
		}

		/* Copy remaining elements of Left[] if any */
		while (i < size1) {
			arr[k] = Left[i];
			i++;
			k++;
		}

		/* Copy remaining elements of Right[] if any */
		while (j < size2) {
			arr[k] = Right[j];
			j++;
			k++;
		}
	}

	// method to print array of size n
	static void printArray(int arr[]) {
		for (int i = 0; i < arr.length; ++i)
			System.out.print(arr[i] + " ");
		System.out.println();
	}

}

OUTPUT

Given Unsorted Array :
11 10 12 4 6 5 

Sorted array :
4 5 6 10 11 12 

Summary

In this tutorial, we saw the concept of merge sorting algorithm and we wrote a recursive merge sorting code in java. I suggest copy this code in your favorite IDE and test it.
I hope you liked it !

---