MergeSort

 We have come now to my favorite sorting algorithm, and, for the first time, one that will need more space than the array we want to sort. This time, the algorithm is mergeSort, which works recursively. This is, incidentally, one of the reasons I like it more than the others—the other reason being that it’s faster, in a way we’ll quantify soon.

MergeSort in plain English is as follows:

• Split the array in half until you’re left with a bunch of individual elements
• Now, take the old arr[0] and old arr[1] and compare them. Put them in the right order, in an array with two elements
• Eventually, you’ll form a bunch of pairs, which, as a pair, will be sorted
• Then, combine those pairs into 4s
• Then combine those 4s into 8s
•  And so on, until you have a sorted array

Again, let’s look at our example:

We have

3

7

2

4

1

5

6

Which we will now split into

3

 

7

 

2

 

4

 

1

 

5

 

6

Now, let’s make couples.

3 and 7 are sorted, so we are fine with:

3

7

2 and 4 are sorted, so we’re fine with

2

4

1 and 5 are sorted, so we’re fine with

1

5

 

6 is sorted by itself so we’re fine with

1

Now, let’s merge (and sort) groups of couples into 4s:

From (3,7) and (2, 4):
The minimum of 2 and 3 is 2, so 2 goes first

2

From (3, 7) and (4):
The minimum of 3 and 4 is 3, so 3 goes next

2

3

From (7) and (4):
The minimum is 4, so 4 goes next

2

3

4

From (7) and ():
All we have left is the 7, so it gets the last spot

2

3

4

7

And now the other half:
From (1, 5) and (6), the minimum is 1, so 1 goes first

1

From (5) and (6) the minimum is 5, so 5 goes next:

1

5

From () and (6), all we have left is the 6, so it takes the last place:

1

5

6

And now we have halves of the array sorted, so we just need one more merge:

From (1, 5, 6) and (2, 3, 4, 7), the minimum is 1:

1

 
Then we take the 2 from the other list:

1

2

Then we stay in the second list to get 3:

1

2

3

Then we stay in the second list (again) to grab the 4:

1

2

3

4

Now we go back to the first list for the 5:

1

2

3

4

5

The 6 also comes from there:

1

2

3

4

5

6

And there’s nothing in one of the lists now, but the other still has just the 7, so it’s our last element, and now everything is properly sorted:

1

2

3

4

5

6

7

We call these extra arrays we need to hold the smaller parts of the set we’re sorting “subarrays” or “auxiliary arrays” or “helper arrays.”


Before you go on, do what I had to do when I first learned this algorithm: make a video or live demo for your family of you mergeSort-ing about that many red Solo cups marked with numbers on their bottoms. If you can correctly sort the cups, move on to the pseudocode.

function mergeSort(A):

    if length(A) <= 1:

        return A

 

    mid = length(A) / 2  

    left = mergeSort(A[0 : mid]) // this creates a left half, from 0 to mid-1

    right = mergeSort(A[mid : length(A)]) // this creates a right half, rom mid to length(A)-1

 

    return merge(left, right)

 

function merge(left, right):

    result = empty array

    while left is not empty and right is not empty:

        if left[0] <= right[0]:

            append left[0] to result

            remove left[0] from left

        else:

            append right[0] to result

            remove right[0] from right

 

    append any remaining elements of left to result

    append any remaining elements of right to result

 

    return result                                 

 

Spend some time with this pseudocode and understand why it is equivalent to the example, or to what you did for your family with the cups. Once you are confident you understand the pseudocode—and only then—move on to the real Java code, found below:

public class MergeSort {

    // Main function to call mergeSort

    public static void main(String[] args) {

        int[] array = {12, 11, 13, 5, 6, 7};

        mergeSort(array, 0, array.length - 1);

        System.out.println("Sorted array:");

        for (int i : array) {

            System.out.print(i + " ");

        }

    }

 

    // Recursive mergeSort function

    public static void mergeSort(int[] array, int left, int right) {

        if (left < right) {

            int mid = (left + right) / 2; // Use division to find the midpoint

            mergeSort(array, left, mid);

            mergeSort(array, mid + 1, right);

            merge(array, left, mid, right);

        }

    }

 

    // Merge function to combine two sorted halves

    public static void merge(int[] array, int left, int mid, int right) {

        int n1 = mid - left + 1;

        int n2 = right - mid;

 

        int[] L = new int[n1];

        int[] R = new int[n2];

 

        for (int i = 0; i < n1; ++i)

            L[i] = array[left + i];

        for (int j = 0; j < n2; ++j)

            R[j] = array[mid + 1 + j];

 

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2) {

            if (L[i] <= R[j]) {

                array[k] = L[i];

                i++;

            } else {

                array[k] = R[j];

                j++;

            }

            k++;

        }

 

        while (i < n1) {

            array[k] = L[i];

            i++;

            k++;

        }

 

        while (j < n2) {

            array[k] = R[j];

            j++;

            k++;

        }

    }

}