8.14. 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: they require in the worst case \(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 ANDlistB
is empty 2 iflistA
is empty 3 move first item fromlistB
to end ofsortedList
4 else iflistB
is empty 5 move first item fromlistA
to end ofsortedList
6 else 7 Note: Items left in both A and B, pick smallest 8 if (first item fromlistA
) <= (first item fromlistB
) 9 move first item fromlistA
to end ofsortedList
10 else 11 move first item fromlistB
to end ofsortedList
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:
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.