Posts with tag "Sorting"

CLRS Algorithms Sorting

MergeSorting a hand of playing cards

So we're still not up to an algorithm a day, but I'm gaining... So far, we've been looking at relatively simple quadratic (i.e. O(n²)) sorting algorithms. These have been incremental algorithms, so that we sort one element, then we sort the next unsorted element, and so on. Another category of algorithms are those known as divide-and-conquer algorithms. In this style of algorithm, we take our entire data set and partition it into smaller, simpler portions, solve each subportion, and then integrate the subportions back together to yield the full result.

Mergesort is a simple example of a divide-and-conquer algorithm, described in Chapter 2.3.1 of CLRS. Perhaps this should really be called divide-conquer-combine, as that more accurately describes what we are doing:

1. Divide: Split our items in half, giving us a left set and a right set each of n/2 items.
2. Conquer: We then need to sort each of these smaller sets, so we recursively apply the divide step on each of the subsets. Trivially, once we have reached subsets of a single item, that subset is sorted, so that is our base case where we stop dividing.
3. Combine: When the two subsets are sorted, we then merge them back together to produce the full sorted set.

You can see this procedure in action in the GIF to the left. Dividing into the left and right subsets is trivial, so the real key is the merging operation. Using cards as an example, this is quite intuitive; when we are merging, what we do is look at the first card in the left set and the first card in the right set. Whichever card is smaller, we strip it off and add it to the merged set, and continue in that fashion until one of the sets is empty, then add all the remaining cards in the non-empty set.

Simple, right? Conceptually, it certainly is, and if I were going to do this with some higher-level constructs like LINQ, it would be a snap to translate almost directly into code, but we're going to do this the hard way, and so that makes it a little more complicated ☺.