Merge sort differs from the other two major O(n log n) algorithms in that it does not require random access to the sequence being sorted.
Merge sort is thus commonly used for sorting linked lists, as well as on-disk structures too large to fit in core. Additionally, merge sort does not require destructive modification, so it can be easily implemented in pure functional languages. For example, in haskell:

merge :: Ord a => [a] -> [a] -> [a]
merge l [] = l
merge [] l = l
merge l@(x:xs) m@(y:ys) =
  if x <= y then x : (merge xs m)
            else y : (merge l ys)

infixl 0 `merge`

oddevn :: [a] -> ([a],[a])
oddevn   []         = ([],[])
oddevn   [x]        = ([x],[])
oddevn   (x:xs)     = let pr = oddevn xs
                      in  (x:snd pr, fst pr)

mergesort :: Ord a => [a] -> [a]
mergesort []  = []
mergesort [x] = [x]
mergesort l   = let pr = oddevn l
                in mergesort (fst pr) `merge` mergesort (snd pr)

A Layman's Guide To Merge Sort

What Is It?

Merge sort is one of many methods used to sort a set of items. It is a particularly useful method to use if you have a large set of items, such as a deck of UNO cards, where it's not efficient to hold all of them in hand and use a bubble sort (which is how many people naturally sort cards or other items).

It is also used very often for sorting large lists in computer science, as it is very advantageous at breaking down large sets into smaller, more manageable sorting tasks.

The Merge: The Fundamental Task

The basic idea behind the merge sort is that you can take two already-ordered sets of items and quickly merge them through a series of simple comparisons. Here's an example of how a merge works:

                             
             X        
           X X       
Step 1:    X X       X
           X X     X X
         X X X     X X
         X X X   X X X
         Set 1   Set 2   Combined Set

As you can see, Step 1 consists of two sets of sticks, both already sorted. Our goal is to merge the two into one sorted set.

                             
             X        
           X X       
Step 2:    X X      X
           X X    X X
         X X X    X X
         X X X    X X    X
         Set 1   Set 2   Combined Set

In Step 2, we compare the first member of each set and see that the first item in set 2 is the smallest, so we add that to the combined set.

                             
            X        
          X X       
Step 3:   X X       X
          X X     X X
          X X     X X      X
          X X     X X    X X
         Set 1   Set 2   Combined Set

In Step 3, we compare the first member of each set and see that the first item in set 1 is the smallest, so we add that to the combined set.

                             
            X        
          X X       
Step 4:   X X      X
          X X      X         X
          X X      X       X X
          X X      X     X X X
         Set 1   Set 2   Combined Set

In Step 4, we compare the first member of each set and see that the first item in set 2 is the smallest, so we add that to the combined set.

                             
            X        
          X X       
Step 5:   X X                  X
          X X                X X
          X X              X X X
          X X            X X X X
         Set 1   Set 2   Combined Set

In Step 5, we compare the first member of each set and see that the first item in set 2 is the smallest, so we add that to the combined set.

                             
                                   X
                                 X X
Step 6:                        X X X
                             X X X X
                           X X X X X
                         X X X X X X
         Set 1   Set 2   Combined Set

In Step 6, we see that set 2 is empty at the start, so we can add the remainder of the already-sorted set 1 to the combined set. Thus, the combined set is already sorted.

A Visual Example of Use of Merge Sort

         X X   X                       
         X X X X       X           X   
         X X X X   X   X X       X X   
Step 1:  X X X X X X   X X       X X   X
         X X X X X X   X X   X   X X   X
         X X X X X X   X X X X   X X X X
         X X X X X X X X X X X X X X X X

Step 1 shows a random distribution of "sticks," of length 1 through 7. We want to sort these using mergesort so that the shortest stick is on the left.

         X X   X                        
         X X X X       X           X    
         X X X X   X   X   X     X X   X
Step 2:  X X X X X X   X   X     X X   X
         X X X X X X   X   X   X X X   X
         X X X X X X   X X X   X X X X X
         X X X X X X X X X X X X X X X X

Step 2 is the result of comparing the members of each pair in the set and putting the smaller one on the left. 1/2, 3/4, 5/6, 7/8, 13/14, and 15/16 were already placed correctly with the small one on the left, but we switched the place of 9/10 and 11/12.

           X X X                        
         X X X X       X               X
         X X X X     X X       X   X X X
Step 3:  X X X X   X X X       X   X X X
         X X X X   X X X     X X   X X X
         X X X X   X X X   X X X X X X X
         X X X X X X X X X X X X X X X X

Step 3 is the step where the sorting procedure becomes visually obvious. Now that we have each pair in order, we merge pairs next to each other (1/2 merges with 3/4; 5/6 merges with 7/8; and so on). This is done by comparing the smallest (i.e., first) member of each pair and then selecting the smallest of those two, then repeating until both pairs are emptied. Thus 1-4 are sorted, as are 5-8, 9-12, and 13-16.

                   X X X                
               X X X X X               X
             X X X X X X         X X X X
Step 4:    X X X X X X X         X X X X
           X X X X X X X       X X X X X
           X X X X X X X   X X X X X X X
         X X X X X X X X X X X X X X X X

Step 4 is a merger of the already-sorted sets 1-4 and 5-8 and also the merger of sets 9-12 and 13-16. This is done by simply comparing the first member of each of the contributing sets and adding the smallest, then repeating until both contributing sets are empty. This leaves two sorted sets, 1-8 and 9-16.

                                   X X X
                             X X X X X X
                     X X X X X X X X X X
Step 5:            X X X X X X X X X X X
                 X X X X X X X X X X X X
             X X X X X X X X X X X X X X
         X X X X X X X X X X X X X X X X

Step 5 shows the complete result. The remaining two already-sorted sets of sticks (1-8 and 9-16) were merged together using the same merger procedure (compare the first one in each set, take the smallest, repeat until both stacks are empty).

Variations on the Theme

There are lots of variations on the merge theme. Some merge sorts merge more than two sets at the same time, selecting the smallest from three or more sets. Other techniques break the large set down into small pieces, sort these pieces using another technique optimized for small sets (such as quicksort), then merge these sorted pieces together.

Personally, I find merge sort not only a useful tool for understanding how to order things for programming, but I also use it for the sorting of items around the house, such as recipes and decks of playing cards, items of which there are a large number and it is unwieldy to use other techniques.

Log in or register to write something here or to contact authors.