Home › Algorithm › Merge Sort

Merge Sort

Posted on Posted in Algorithm, Java Tagged with , ,

Consider the problem of sorting an array of numbers in order. Merge sort is to recursively divide the array in half, and then recombine the sorted subarrays.

  • Divide the array in half.
  • Recursively divide until each subarray has only one element.
  • Merge the sorted subarrays.

The following example shows how an array is divided and then merged.

  38     27     43      3      9     82     10      -- divide
  38     27     43      3  |   9     82     10
  38     27  |  43      3  |   9     82  |  10
  38  |  27  |  43  |   3  |   9  |  82  |  10      -- each length=1

  27     38  |   3     43  |   9     82  |  10      -- merge
  3      27     38     43  |   9     10     82
  3      9      10     27     38     43     82

The following method implements merge sort in Java. It is a recursive method which calls itself on the subarrays.

public static void mergeSort(int[] data, int first, int last)
{
    if (first >= last)
        return;
    int mid = (first + last) / 2;

    mergeSort(data, first, mid);      // sort the left half
    mergeSort(data, mid + 1, last);   // sort the right half

    merge(data, first, last);         // merge two sorted subarrays
}

The following is the method for merging two sorted subarrays. The first subarray starts from the index first and ends at the index mid, and the second subarray starts from the index mid + 1 and ends at index last. It keeps picking up the smaller element from the two subarrays, until one subarray is finished; and then it copies the rest of the other subarray to the result.

public static void merge(int[] data, int first, int last)
{
    // A new array to hold the merged result
    int[] temp = new int[last - first + 1];

    int mid = (first + last) / 2;
    int i = first, j = mid + 1, k = 0;

    // Copy smaller item from each subarray into temp until one
    // of the subarrays is exhausted
    while (i <= mid && j <= last)
    {
        if (data[i] < data[j])
            temp[k++] = data[i++];
        else
            temp[k++] = data[j++];
    }

    // Copy remaining elements from first subarray, if any
    while (i <= mid)
        temp[k++] = data[i++];

    // Copy remaining elements from second subarray, if any
    while (j <= last)
        temp[k++] = data[j++];

    // Copy the result back into original array
    for (i = first; i <= last; i++)
        data[i] = temp[i - first];
}

Note that in the statement temp[k++] = data[j++], we use postfix increment operator ++. A postfix expression (like j++) evaluates to be the value of the variable before incremented. For example, the following statement

a = i++;

has equivalent consequence as the following two statements:

a = i;
i = i + 1;

And the following

temp[k] = data[i++];

is equivalent to

temp[k] = data[i];
i = i + 1;

And

temp[k++] = data[i++];

is equivalent to

temp[k] = data[i];
k = k + 1;
i = i + 1;

An alternative solution for merging is given below.

public static void merge(int[] data, int first, int last)
{
    int mid = (first + last) / 2;
    int i = first, j = mid + 1;
    int len = last - first + 1;
    int[] temp = new int[len];      // Temporary storage

    for (int k = 0; k < len; k++)
    {
        if (i == mid + 1)           // The left part is done
            temp[k] = data[j++];
        else if (j == last + 1)     // The right part is done
            temp[k] = data[i++];
        else if (data[i] < data[j]) // Get one from the left
            temp[k] = data[i++];
        else                        // Get one from the right
            temp[k] = data[j++];
    }

    // Copy merged part back into the original array
    for (i = first; i <= last; i++)
    data[i] = temp[i - first];
}

Suppose the array has length n. The merge sort approach recursively divides the array in half, and this generates totally log(n) levels of divisions, and in consequence, log(n) levels of merging. For each level, merging runs in linear time. The total running time is about O(n * log(n)). This is much more efficient than selection/insertion/bubble sorts which run in O(n^2) time.

Merge sort uses the idea of divide and conquer:

  • Recursively break down a problem into two (or more) sub-problems of the same type, until they become simple enough to be solved directly.
  • The solutions to the sub-problems are then combined to give a solution to the original problem.

Demos of merge sort:
http://www.sorting-algorithms.com/merge-sort
http://youtu.be/XaqR3G_NVoo

Related Posts

Comments

comments