Software Physics

Merge sort is another simple algorithm that introduces a fairly powerful concept: Divide and Conquer. Like the previous example, we’ll look at the algorithm, a Lisp implementation then look a bit at running time.

The Algorithm

First let’s consider the divide-and-conquer aspect of the algorithm. The basic idea here is that one way of simplifying a hard problem is to break it up into smaller, easier ones. For sorting algorithms, we look at whether attacking the whole sorting problem can be simplified by attacking a collection of smaller sorts.

To evolve merge sort, let’s consider the premise that sorting smaller lists is easier than sorting bigger lists. Let’s ignore, for the moment, whether this makes sense or in what way doing a lot of easy tasks is better than attempting one big task or any other unanswered philosophical questions. Let’s just consider an algorithm that sorts a list by breaking it into smaller lists, sorting those lists, then combining the sorted lists back into a single sorted entity.

Now let’s consider the “…combining the sorted lists back into a single sorted entity”.

Combining two sorted lists into a single list is a pretty easy task when you look think a bit about it. Let’s consider two sorted lists, as piles of cards A and B and a third pile C which will receive the result of our merger operation. Let’s furthermore assume that A and B are sorted with lowest values on top and that we will create a sorted pile C where the lowest values are at the bottom of the pile.

The merge algorithm is straightforward. Look at the top of piles A and B and put the smallest card on top of pile C; repeat until no more cards are in either piles A or B.  I don’t think this needs much explanation, a little thought should convince you that this is all you have to do to successfully merge two sorted piles into a third. Note that the total number of steps required to merge the two piles will be the sum of the cards in each pile, which is the total number of cards to sort; the merge algorithm is O(n).

Ok, so much for merging. We’ve yet to address sorting and why/if sorting smaller piles is easier than sorting big piles. Certainly if n is really big then n/2 is really big too and my problem didn’t get notably easier sorting the two smaller but, nevertheless, still really big, lists. However, if we keep dividing and keep suspending our frustration that we haven’t addressed the sorting question, we eventually reach the end of the line where we’re sorting either one or two element lists. Now, “this seems stupid” you (I) say, “how does this help?” All we’ve demonstrated is that sorting lists of one or two items is easier than sorting lists of a million. We’re geniuses.

So let’s consider how this pathologically smaller sort helps.

Let’s assume that our algorithm consists of a merge function, a sort function and a sort-stupid function where sort-stupid is a sorter that handles lists of one or two elements. We’re going to build sort using sort-stupid; sort is pathetically lazy if sort is passed an array other than a one or two element array, it divides the array into two halves and attempts to merge the result of performing the sort function (itself) on the smaller arrays. As is obvious, sort will keep procrastinating (recursing) until the original list has been chopped up into stupid-sort-sized pieces. At that point the sort does the trivial sort, calling stupid-sort, and returns the trivial result. The recursion will unwind merging first the trivial lists then lists of ever-increasing size until we’ve returned the final sorted list.

Pretty neat.

The Code

Here’s a chunk of common lisp code that implements the algorithm.

;; Sort ascending
(defun merge-sort (the-list)
  (if (> (length the-list) 2)
      (setf the-list
	(merge-lists-ascending
	    (merge-sort (upper-half the-list))
	    (merge-sort (lower-half the-list))))
      (when (and (> (length the-list) 1)
 	         (> (first the-list) (second the-list)))
	             (rotatef (first the-list) (second the-list))))
   the-list)

[Note: As the first commenter to this post pointed out, I’m not a Lisp expert. As I mentioned here I’m using this exercise, in part, as a way to learn the language. Also, one of the attractions of using Lisp for the exercise was that I could write examples which were nearly as clear as had I written them in some sort of pseudo-code; the examples will not necessarily be efficient. Hopefully as I get better with the language I can figure out how to be both expressive and efficient]

I didn’t bother to split out stupid-sort; it was a cute bit for the narrative but isn’t necessary in the code. The code implements the algorithm as described; if we’re passed a list larger than one or two items, we “give up” and attempt to merge two lists half-lists. Otherwise, we check to see if it’s a list of more than one element and if the list is not already in ascending order (already sorted). If the list is not ascending, then we swap the elements.

For completeness, let’s look at the helper functions used in the algorithm above.

While it’s not hard to split the list up into an upper and a lower half, the resultant code clutters the algorithm so I used macros to pull the junk out of the way. The lower half or the array is the subsequence starting a 0 and having a length of ceiling(total-length/2). The upper half starts ant ceiling(total-length/2) and runs to the end of the array. Here’s the macros that implement upper-half and lower-half.

(defmacro do-half (seq lower)
  `(subseq ,seq ,@(append (when lower '(0)) `((ceiling (/ (length ,seq) 2))))))

(defmacro upper-half (seq)
  `(do-half ,seq nil))

(defmacro lower-half (seq)
  `(do-half ,seq t))

The upper and lower split operations are almost identical specifically, the upper split looks like

(subseq seq (ceiling((/ (length seq) 2)))

and the lower half looks like

(subseq seq 0 (ceiling((/ (length seq) 2)))

As you can see the only difference is the 0. For the upper and lower macros, cut-and-paste would work but it’s not just repetitive, there is a practical danger that you could change the rounding sense at some point and not catch it in both places. Anyway, it’s a bit retentive but I split the common code out of the upper/lower macros and created a third macro. I like it better and it expands to the same code at the end of the day regardless.

The merge routine cheats a bit; lisp implements a merge function so I simply wrapped it in a macro, again, to make the algorithm code more readable.

(defmacro merge-lists-ascending (l1 l2)
  `(merge 'list ,l1 ,l2 #'<))

Running Time

There are two important components to the running time, the number of splits that we perform and the number of operations consumed by the merge function at each split. Consider the following diagram.

Each set of boxes represents the size of the list being merged at each stage. Note that at each stage there are 2^k lists to merge each of length n/2^k where n is the length of the original list and k is the stage (round). The total number of steps in the merge, we noted earlier, is equal to the sum of the lengths of the lists being merged. Therefore, at each stage, the total number of merge operations is 2^k * n/2^k = n. Which says that, regardless of which level we’re at, we execute n operations performing the merges.

Now all that’s left is to determine the number of levels, k, in terms of n which is given by k = log₂(n). The running time of the algorithm is given by k*n therefore, the total running time of the algorithm is proportional to nlog₂(n) and therefore the algorithm is O(nlog(n)). Note that we made no assumptions about input so this is both best and worst case running time.

So there’s #2 of like a zillion. more fun to come!