Merge sort

Computers use a smart way to sort lists.

It starts with a big, messy list. The computer breaks the list into tiny parts. Each part has only one item. One item is always in order.

Then, the computer joins the parts back together. It puts them in the right order as it merges them. It keeps doing this until only one list is left. Now, the whole list is sorted! This method was made by a man named John von Neumann. It helps computers work very fast.

Computers need to put lists in order. This is called sorting. One smart way to do this is called merge sort.

This method was invented by John von Neumann in 1945. It uses a way called divide-and-conquer. This means the computer breaks a big job into small parts.

First, the computer takes a messy list. It splits the list into many small sub-lists. It keeps splitting them until each list has only one item. A list with one item is already sorted.

Next, the computer starts to merge the parts. Merging means joining two sorted lists into one new list. The computer compares the items to keep them in order. It does this over and over. It keeps merging until only one big list remains. Now, the whole list is sorted!

Merge sort is very efficient. This means it works well and saves time. It is also a stable sort. This means if two items are the same, their order stays the same.

This helps keep data organized and correct.

Computers often need to organize lists of information. This task is called sorting. One very smart way to do this is called merge sort.

It is a general-purpose way to sort things by comparing them. Many versions of merge sort are stable. This means that if two items are the same, they stay in their original order. This helps keep data organized and correct.

Merge sort works by using a method called divide-and-conquer. This means the computer breaks a big job into smaller, easier parts. First, the computer takes a messy, unsorted list. It divides that list into many smaller sub-lists. It keeps splitting them until every sub-list has only one element. A list with just one element is already considered sorted.

Once the pieces are small, the computer begins to merge them. Merging is the way the computer joins two sorted sub-lists to make a new one. The computer looks at the items and puts them in the right order. It repeats this step over and over again. Each time, the new sub-lists get longer and more organized. This continues until only one single list remains. That last list is the fully sorted version of the original.

This clever way of sorting was invented by John von Neumann in 1945. Later, in 1948, Goldstine and von Neumann wrote a report about a version called bottom-up merge sort.

This method is very efficient. It is good at sorting because merging two already sorted lists happens in linear time. This means it does not take a huge amount of extra steps. For very large lists, it can even be faster than other methods like quicksort.

There are different ways to use this idea. A top-down version splits the list from the top down. A bottom-up version starts with tiny lists and builds them up. Some versions even look for "natural runs." These are parts of a list that are already sorted by chance. By finding these, the computer can do its job even faster. This helps merge sort work well in many different computer languages.

In computer science, merge sort is a highly efficient and general-purpose sorting algorithm. It is categorized as a comparison-based algorithm, meaning it organizes data by comparing the values of different elements. One of its most important features is that it is often stable. In a stable sort, the relative order of equal elements remains the same between the input and the final output. This stability is vital when sorting complex data where the original order of certain items must be preserved.

Merge sort operates using a strategy known as divide-and-conquer. This method breaks a large, complex problem into smaller, more manageable sub-problems. The process begins by taking an unsorted list of $n$ elements and dividing it into $n$ sub-lists. Each of these sub-lists contains only one single element. Because a list with only one item is considered sorted by definition, the algorithm has reached its simplest state. The algorithm then repeatedly merges these sub-lists to create new, larger sorted sub-lists. This cycle continues until only one single sub-list remains, which is the fully sorted version of the original data.

There are two primary ways to implement this mechanism: top-down and bottom-up. In a top-down implementation, the algorithm uses recursion to split the list. It finds the midpoint of the array and calls itself on the left and right halves. This continues until it reaches the base case of a single-element run. In a bottom-up implementation, the algorithm avoids recursion. Instead, it starts with sub-lists of size one and iteratively merges them into larger runs of length 2, 4, 8, and so on. This process continues until the entire array is sorted.

The history of merge sort is tied to the very beginnings of modern computing. The algorithm was invented by John von Neumann in 1945. Shortly after, in 1948, Goldstine and von Neumann published a report providing a detailed description and analysis of the bottom-up version. These early developments were essential for managing the large datasets processed by early machines.

Efficiency is a key reason why merge sort is so widely used. The algorithm has an average and worst-case performance of $O(n \log n)$ comparisons. This means the time it takes to sort grows predictably as the list gets larger. The running time $T(n)$ can be described by the recurrence relation $T(n) = 2T(n/2) + n$. This formula shows that the algorithm performs two tasks on half-sized lists and then spends $n$ steps merging them. In the worst case, merge sort can use approximately 39% fewer comparisons than the average case of the quicksort algorithm.

Researchers have developed several specialized variations of the algorithm to improve performance. Natural merge sort is one such version. It is similar to bottom-up merge sort but exploits "natural runs." These are sequences of numbers within the input that are already sorted by chance. By identifying these runs, the algorithm can complete its task in fewer passes. In the best-case scenario, where the input is already sorted, a natural merge sort only needs to make one pass. Another variation is the ping-pong merge sort, which merges four blocks at once instead of two. This method can reduce the total number of moves by half.

While merge sort is powerful, it does have specific requirements regarding memory. Most common implementations do not sort "in-place." This means the computer must allocate extra memory to store the sorted output, roughly equal to the size of the input. This is a notable difference from some versions of quicksort. However, merge sort remains highly effective for certain types of data. It is particularly popular in languages like Lisp, where data structures are often accessed sequentially rather than jumping to specific locations. This makes it a fundamental tool in the study of algorithmic complexity and data organization.