NB I’ve been a mostly self-taught programmer since I was in middle school (about 20 years now). I’m in the processing of teaching myself some of the things I missed out on by not having a Computer Science education; I’m also new to Ruby. This post is me writing out my thoughts on this subject to better understand it for myself — maybe someone else will find it useful, but don’t mistake me for an expert.
Mergesort is a classic “divide and conquer” algorithm for sorting an array. We have a problem like this:
- Input: An unsorted array of numbers, e.g.
[1, 4, 3, 9].
- Output: The input array, sorted from least to greatest, e.g.
[1, 3, 4, 9].
Mergesort works by splitting the input array into progressively smaller sorted arrays and then merging those sorted arrays together to produce the final sorted array.
Here is an implementation of mergesort I wrote in Ruby. I’ll break it down in the rest of this post.
Mergesort is split into two functions: a function
mergesort which splits the array into smaller pieces and calls the
merge function on those smaller pieces, and another function, the
merge function, which combines two already-sorted arrays into a single sorted array.
Let’s look at the
merge function first.
The merge function takes two arrays,
right, as parameters. It goes through each array element by element comparing them — if the
left array’s element is smaller, it takes that element from the
left array and adds it to a new
sorted array; then it compares the next
left element with the same
right element. It does this until both
right arrays are empty, then returns the
If I pass
merge(, ) it returns
merge([0, 2], [1, 3]) returns
[0, 1, 2, 3].
merge([9, 1], [2, 3]), though, returns
[2, 3, 9, 1] because
merge isn’t a sorting algorithm on its own — it just merges together two already-sorted arrays. We need to pass
merge already-sorted arrays in order for it to work.
mergesort does that by splitting the input array into successively smaller arrays, splitting the input array in half and recursively calling itself on the two halves until it reaches two arrays of size 11. Once it has two arrays of size 1, it calls
merge on those two arrays and starts building up a single sorted array out of progressively larger sorted array inputs.
Adding some output to the program shows what’s going on a little more clearly.
Running that outputs:
You could visualize it like this:
I hope that makes things clear! I think I will save analyzing the runtime complexity2 or discussions of when to use mergesort versus other sorting algorithms as exercises for the reader, or maybe future blog posts.
1 Assuming an initial input array of size 2 or more — otherwise it would just return its input.
2 The diagram above would be a good starting point.