# 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: 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 sortedList1 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 7Note: Items left in both A and B, pick smallest8 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:

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.