8.15. Merging

A problem-solving method that is often utilized in computer science is called divide-and-conquer. In this paradigm, a problem is repeatedly divided into smaller and smaller sub-problems, until the solution to individual sub-problems becomes obvious. The solutions to these sub-problems are then combined to form a solution to the original problem.

The sorting algorithms we have learned to this point (Insertion sort and Selection sort) have been quadratic time algorithms: in the worst case, they require \(O(n^2)\) amount of time to sort n items. There are a number of sorting algorithms that perform much better than that - a common feature of most of them is some kind of reliance on a divide-and-conquer strategy. The algorithm we are going to examine is Merge Sort.

One of the keys to Merge Sort is an algorithm for merging two sorted lists into one big sorted list. We won’t worry about computer pseudocode for this process, but here is human pseudocode:

1   How to Merge listA and listB into sortedList
1   repeat until listA is empty AND listB is empty
2       if listA is empty
3           move first item from listB to end of sortedList
4       else if listB is empty
5           move first item from listA to end of sortedList
6       else
7           Note: Items left in both A and B, pick smallest
8           if (first item from listA) <= (first item from listB)
9               move first item from listA to end of sortedList
10          else
11              move first item from listB to end of sortedList

The video below demonstrates the process:

Think you have it? Give it a try below. Use the ListA and ListB buttons to move an item from the two sorted lists at the bottom to the new list at the top:

Animation based on work by Y. Daniel Liang

Once you have merging down, move on to Merge Sort on the next page. Remember for later what was mentioned at the end of the video - merging n items is a linear algorithm - it takes \(O(n)\) work.

You have attempted of activities on this page