Merge Sort

The merge sort algorithm can be described recursively as follows: The algorithm divides the array into two halves and applies a merge sort on each half recursively. After the two halves are sorted, merge them.

The algorithm for a merge sort is given in code below:

public static void mergeSort(int[] list) {
if (list.length > 1) {
mergeSort(list[0 ... list.length / 2]);
mergeSort(list[list.length / 2 + 1 ... list.length]);
merge list[0 ... list.length / 2] with
list[list.length / 2 + 1 ... list.length];
}
}

Figure below illustrates a merge sort of an array of eight elements (2 9 5 4 8 1 6 7). The original array is split into (2 9 5 4) and (8 1 6 7). Apply a merge sort on these two subarrays recursively to split (2 9 5 4) into (2 9) and (5 4) and (8 1 6 7) into (8 1) and (6 7). This process continues until the subarray contains only one element. For example, array (2 9) is split into the subarrays (2) and (9). Since array (2) contains a single element, it cannot be further split. Now merge (2) with (9) into a new sorted array (2 9); merge (5) with (4) into a new sorted array (4 5). Merge (2 9) with (4 5) into a new sorted array (2 4 5 9), and finally merge (2 4 5 9) with (1 6 7 8) into a new sorted array (1 2 4 5 6 7 8 9).

The recursive call continues dividing the array into subarrays until each subarray contains only one element. The algorithm then merges these small subarrays into larger sorted subarrays until one sorted array results.

The merge sort algorithm is implemented in the code below:

package demo;

public class MergeSort {
    /** The method for sorting the numbers */
    public static void mergeSort(int[] list) {
        if(list.length > 1) {
            // Merge sort the first half
            int[] firstHalf = new int[list.length / 2];
            System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
            mergeSort(firstHalf);

            // Merge sort the second half
            int secondHalfLength = list.length - list.length / 2;
            int[] secondHalf = new int[secondHalfLength];
            System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
            mergeSort(secondHalf);

            // Merge firstHalf with seocndHalf into list
            merge(firstHalf, secondHalf, list);
        }
    }

    /** Merge two sorted lists */
    public static void merge(int[] list1, int[] list2, int[] temp) {
        int current1 = 0; // Current index in list1
        int current2 = 0; // Current index in list2
        int current3 = 0; // Current index in temp

        while(current1 < list1.length && current2 < list2.length) {
            if(list1[current1] < list2[current2])
                temp[current3++] = list1[current1++];
            else
                temp[current3++] = list2[current2++];
        }

        while(current1 < list1.length)
            temp[current3++] = list1[current1++];

        while(current2 < list2.length)
            temp[current3++] = list2[current2++];
    }

    public static void main(String[] args) {
        int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
        mergeSort(list);
        for(int i = 0; i < list.length; i++)
            System.out.print(list[i] + " ");
    }

}

The mergeSort method (lines 5–21) creates a new array firstHalf, which is a copy of the first half of list (line 9). The algorithm invokes mergeSort recursively on firstHalf (line 10). The length of the firstHalf is list.length / 2 and the length of the secondHalf is list.length - list.length / 2. The new array secondHalf was created to contain the second part of the original array list. The algorithm invokes mergeSort recursively on secondHalf (line 16). After firstHalf and secondHalf are sorted, they are merged to list (line 19). Thus, array list is now sorted.

The merge method (lines 24–41) merges two sorted arrays list1 and list2 into array temp. current1 and current2 point to the current element to be considered in list1 and list2 (lines 25–27). The method repeatedly compares the current elements from list1 and list2 and moves the smaller one to temp. current1 is increased by 1 (line 31) if the smaller one is in list1 and current2 is increased by 1 (line 33) if the smaller one is in list2. Finally, all the elements in one of the lists are moved to temp. If there are still unmoved elements in list1, copy them to temp (lines 36–37). If there are still unmoved elements in list2, copy them to temp (lines 39–40).

Figure below illustrates how to merge the two arrays list1 (2 4 5 9) and list2 (1 6 7 8). Initially the current elements to be considered in the arrays are 2 and 1. Compare them and move the smaller element 1 to temp, as shown in Figure below (a). current2 and current3 are increased by 1. Continue to compare the current elements in the two arrays and move the smaller one to temp until one of the arrays is completely moved. As shown in Figure below (b), all the elements in list2 are moved to temp and current1 points to element 9 in list1. Copy 9 to temp, as shown in Figure below (c).

The mergeSort method creates two temporary arrays (lines 8, 14) during the dividing process, copies the first half and the second half of the array into the temporary arrays (lines 8, 15), sorts the temporary arrays (lines 10, 16), and then merges them into the original array (line 19), as shown in Figure below (a). You can rewrite the code to recursively sort the first half of the array and the second half of the array without creating new temporary arrays, and then merge the two arrays into a temporary array and copy its contents to the original array, as shown in Figure below (b).

A merge sort can be implemented efficiently using parallel processing.

Let T(n) denote the time required for sorting an array of n elements using a merge sort. Without loss of generality, assume n is a power of 2. The merge sort algorithm splits the array into two subarrays, sorts the subarrays using the same algorithm recursively, and then merges the subarrays. Therefore,

T(n) = T(n / 2) + T(n / 2) + mergetime

The first T(n / 2) is the time for sorting the first half of the array, and the second T(n / 2) is the time for sorting the second half. To merge two subarrays, it takes at most n - 1 comparisons to compare the elements from the two subarrays and n moves to move elements to the temporary array. Thus, the total time is 2n - 1. Therefore,

The complexity of a merge sort is O(n logn). This algorithm is better than selection sort, insertion sort, and bubble sort, because the time complexity of these algorithms is O(n^2). The sort method in the java.util.Arrays class is implemented using a variation of the merge sort algorithm.