Merge Sort Implementation in Java to Sort An Array of Integers

Merge Sort Animation. Source: Wikipedia / CC

Merge Sort is  comparison based divide and conquer algorithm to sort data. This sort can be implemented recursively.

Algorithm Steps:

1. If the number of items to sort is 0 or 1, return
2. Sort the first and second half of the array recursively
3. Merge the two sorted halves into a sorted array.

Complexity:

• Base Case: O(nlogn)
• Average Case: O(nlogn)
• Worst Case: O(nlogn)

Java Implementation Of Merge Sort:

```package com.icodejava.blog;

import java.util.Arrays;

/**
* @author Kushal Paudyal
* www.icodejava.com
* Created On -  Feb 20, 2014
*
* MERGE SORT STEPS
* If the number of items to sort is 0 or 1, return
* Sort the first and second half of the array recursively
* Merge the two sorted halves into a sorted array.
*
* COMPLEXITY:
* Base Case: nlogn
* Average Case: nlogn
* Worst Case: nlogn

*/
public class MergeSort {

public static void main(String args[]) {

int[] numberArray = { 5, 4, 7, 3, 3, 9, 0, -11, 2, 8, 6 };

sort(numberArray);
}

private static void sort(int[] numberArray) {

System.out.println("\nINPUT ARRAY:" + Arrays.toString(numberArray));

int[] tempArray = new int[numberArray.length];

mergeSort(numberArray, tempArray, 0, numberArray.length - 1);

System.out.println("SORTED ARRAY:" + Arrays.toString(numberArray));

}

private static void mergeSort(int[] data, int[] tempArray, int low, int high) {
/** If low is smaller than high, array is not sorted, otherwise it is. */
if (low < high) {

int middle = (low + high) / 2;

System.out.println(" Divide Step -  low:" + low + " middle:" + middle + " high:" + high);

/** Recursively Sort the left side of the array **/
mergeSort(data, tempArray, low, middle);

/** Recursively Sort the right side of the array **/
mergeSort(data, tempArray, middle + 1, high);

/** Merge the sorted arrays **/
merge(data, tempArray, low, middle, high);
}
}

/**
*
* @param data
*            - Original Unsorted or Partially Sorted Array
* @param tempArray
*            - Temporary Helper Array
* @param low
*            - Starting Index of Left Array
* @param middle
* @param high
*            - Ending Index of Right Array
*
*            This method merges two sorted portions of an array using
*            temporary array.
*/
private static void merge(int[] data, int[] tempArray, int low, int middle, int high) {

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

int i = low; // Start of Left Array
int j = middle + 1; // Start of right Array
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 (tempArray[i] <= tempArray[j]) {
data[k] = tempArray[i];
i++;
} else {
data[k] = tempArray[j];
j++;
}
k++;
}
// Copy the rest of the left side of the array into the target array
while (i <= middle) {
data[k] = tempArray[i];
k++;
i++;
}

System.out.println("   Merge Step (low:" + low + ",middle:" + middle + ",high:" + high + ") Original "
+ Arrays.toString(data) + " Temporary" + Arrays.toString(tempArray));

}

}

```

The output of running above program. The intermediates steps have been printed for the helping the readers understand the working of this sorting. You might have to scroll right to view the full output.

```INPUT ARRAY:[5, 4, 7, 3, 3, 9, 0, -11, 2, 8, 6]
Divide Step -  low:0 middle:5 high:10
Divide Step -  low:0 middle:2 high:5
Divide Step -  low:0 middle:1 high:2
Divide Step -  low:0 middle:0 high:1
Merge Step (low:0,middle:0,high:1) Original [4, 5, 7, 3, 3, 9, 0, -11, 2, 8, 6] Temporary[5, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Merge Step (low:0,middle:1,high:2) Original [4, 5, 7, 3, 3, 9, 0, -11, 2, 8, 6] Temporary[4, 5, 7, 0, 0, 0, 0, 0, 0, 0, 0]
Divide Step -  low:3 middle:4 high:5
Divide Step -  low:3 middle:3 high:4
Merge Step (low:3,middle:3,high:4) Original [4, 5, 7, 3, 3, 9, 0, -11, 2, 8, 6] Temporary[4, 5, 7, 3, 3, 0, 0, 0, 0, 0, 0]
Merge Step (low:3,middle:4,high:5) Original [4, 5, 7, 3, 3, 9, 0, -11, 2, 8, 6] Temporary[4, 5, 7, 3, 3, 9, 0, 0, 0, 0, 0]
Merge Step (low:0,middle:2,high:5) Original [3, 3, 4, 5, 7, 9, 0, -11, 2, 8, 6] Temporary[4, 5, 7, 3, 3, 9, 0, 0, 0, 0, 0]
Divide Step -  low:6 middle:8 high:10
Divide Step -  low:6 middle:7 high:8
Divide Step -  low:6 middle:6 high:7
Merge Step (low:6,middle:6,high:7) Original [3, 3, 4, 5, 7, 9, -11, 0, 2, 8, 6] Temporary[4, 5, 7, 3, 3, 9, 0, -11, 0, 0, 0]
Merge Step (low:6,middle:7,high:8) Original [3, 3, 4, 5, 7, 9, -11, 0, 2, 8, 6] Temporary[4, 5, 7, 3, 3, 9, -11, 0, 2, 0, 0]
Divide Step -  low:9 middle:9 high:10
Merge Step (low:9,middle:9,high:10) Original [3, 3, 4, 5, 7, 9, -11, 0, 2, 6, 8] Temporary[4, 5, 7, 3, 3, 9, -11, 0, 2, 8, 6]
Merge Step (low:6,middle:8,high:10) Original [3, 3, 4, 5, 7, 9, -11, 0, 2, 6, 8] Temporary[4, 5, 7, 3, 3, 9, -11, 0, 2, 6, 8]
Merge Step (low:0,middle:5,high:10) Original [-11, 0, 2, 3, 3, 4, 5, 6, 7, 8, 9] Temporary[3, 3, 4, 5, 7, 9, -11, 0, 2, 6, 8]
SORTED ARRAY:[-11, 0, 2, 3, 3, 4, 5, 6, 7, 8, 9]
```