Merge Sort

Merge sort is a sorting algorithm that uses the divide and conquer strategy to sort a list of elements. The algorithm works by dividing the list into smaller sublists, sorting the sublists, and then merging the sorted sublists to produce a sorted list.

Merging two unsorted lists #

Before we discuss the merge sort algorithm, let’s first discuss how to merge two sorted lists. This is a crucial step in the merge sort algorithm.

Consider two unsorted lists

left = [7, 5, 3, 2]
right = [6, 8, 4, 1]

merged = []

First we would need to find the smallest element in the two lists. This would require iterating through the two lists to find the smallest values of the two lists.

This is the value 1 in the right list. We would then remove the value 1 from the right list and add it to the merged list.

We would then find the next smallest value in the two lists, which is 2 in the left list. We would then remove the value 2 from the left list and add it to the merged list.

This is repeated until both lists are empty.

Notice that this involved iterating through boths lists multiple times, and is not an efficient way to merge two lists.

Merging two sorted lists #

If the two lists were instead sorted, we could merge the two lists in a single iteration by comparing the first elements of the two lists, and adding the smaller of the two to the merged list.

Consider two sorted lists

left = [2, 3, 5, 7]
right = [1, 4, 6, 8]

merged = []

So comparing just the first elements of the two lists, we find that 1 is smaller than 2, so we add 1 to the merged list and remove it from the right list.

left = [2, 3, 5, 7]
right = [4, 6, 8]

merged = [1]

We then compare the first elements of the two lists again, and find that 2 is smaller than 4, so we add 2 to the merged list and remove it from the left list.

left = [3, 5, 7]
right = [4, 6, 8]

merged = [1, 2]

We continue this process until we have merged the two lists.

step 3

left = [3, 5, 7]
right = [4, 6, 8]

# compare 3 and 4, add 3 to merged list, remove 3 from left list
left = [5, 7]
right = [4, 6, 8]
merged = [1, 2, 3]

This is repeated for steps 4, to 8, and the merged list contains all the elements of the two lists in the correct order.

step 8

left = []
right = [8]

# add 8 to merged list, remove 8 from right list
left = []
right = []
merged = [1, 2, 3, 4, 5, 6, 7, 8]

Merge Sort Algorithm #

The merge sort uses a similar approach to merge two sorted lists to sort a list of elements. But instead of merging two lists, the merge sort algorithm divides the list into smaller sublists, sorts the sublists, and then merges the sorted sublists to produce a sorted list. This is the divide and conquer strategy.

Here is an unsorted list

Divide #

The list is divided into two sublists

Then the sublists are divided into smaller sublists

This process is repeated until the sublists are of size 1.

Conquer #

The single element sublists are then sorted in two element sublists, then four element sublists, and so on. The merging of the sorted sublists involves comparing the first elements of the two sublists, and adding the smaller of the two to the merged list.

First single element sublists are sorted into two element sublists

Then the two element sublists are sorted into four element sublists, using the merging process described above.

Finally the four element sublists are merged into an eight element sublist.

Implementation of Merge Sort using Recursion #

The merge sort algorithm can be implemented using recursion. The algorithm can be represented as follows.

import java.util.List;

public class MergeSort {
    public List<Integer> mergeSort(List<Integer> list) {
        // base case
        if (list.size() <= 1) {
            return list;
        }

        // divide the list into two sublists
        int middle = list.size() / 2;

        // recursively sort the sublists
        List<Integer> left = mergeSort(list.subList(0, middle));
        List<Integer> right = mergeSort(list.subList(middle, list.size()));

        // merge the sorted sublists
        return merge(left, right);
    }

    public List<Integer> merge(List<Integer> left, List<Integer> right) {
        // create a new list to store the merged list
        List<Integer> merged = new ArrayList<>();

        int leftIndex = 0;
        int rightIndex = 0;

        // compare the left and right lists and add the smaller of 
        // the two to the merged list
        while (leftIndex < left.size() && rightIndex < right.size()) {
            if (left.get(leftIndex) < right.get(rightIndex)) {
                merged.add(left.get(leftIndex));
                leftIndex++;
            } else {
                merged.add(right.get(rightIndex));
                rightIndex++;
            }
        }

        // add the remaining elements of the left and right lists 
        // to the merged list
        while (leftIndex < left.size()) {
            merged.add(left.get(leftIndex));
            leftIndex++;
        }

        while (rightIndex < right.size()) {
            merged.add(right.get(rightIndex));
            rightIndex++;
        }

        return merged;
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        List<Integer> list = Arrays.asList(33, 67, 21, 88, 56, 71, 14, 91);
        List<Integer> sortedList = mergeSort.mergeSort(list);
        System.out.println(sortedList);
    }
}

Note, that the merge process does not actually remove elements from the lists, but instead uses two indices to keep track of the elements that have been merged, leftIndex and rightIndex.