Merge Sort Algorithm in Java

The merge sort algorithm is a divide and conquer algorithm that divides the array into two equal parts and applies merge sort on each half recursively. After the two parts are sorted, then both parts are merged again. The algorithm is illustrated in below figure:

Merge Sort illustration

The above illustration show 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 merge sort on these two subarrays recursively to split (1 9 5 4) into (1 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 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 merge sort algorithm is implemented in below code Listing.

MergeSort.java

public class MergeSort {

       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 secondHalf

                     int[] temp = merge(firstHalf, secondHalf);

                     System.arraycopy(temp, 0, list, 0, temp.length);

              }

       }

       /** Merge two sorted lists */

       private static int[] merge(int[] list1, int[] list2) {

              int[] temp = new int[list1.length + list2.length];

              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++];

              }

              return temp;

       }

       /** A test method */

       public static void main(String[] args) {

              int[] list = { 2, 9, 5, 4, 8, 1, 6, 7, };

              mergeSort(list);

              for (int i = 0; i < list.length; i++) {

                     System.out.print(list[i] + " ");

              }

       }

}

The output of this program is:

    1 2 4 5 6 7 8 9  


Reference(s): Introduction to JAVA by Y. Daniel Liang