Merge Sort

Recently, I was reviewing CS Fundamentals for an upcoming technical interview and was trying to spot the main differences amongst the various comparison sorts. As a teacher, I always taught my students that the best way to learn something is to write about it with the intention of being able to teach someone else. It also helps to find how something is different from another thing to help solidify your knowledge.

Divide with Recursion

Mergesort works through divide and conquer, in that we take an array and divide it in half and continuously divide it until we have sublists. An array that looks like this:

[6, 1, 12, 2, 45, 7]

would look like this using a recursive approach:

[[6], [1], [12], [2], [45], [7]]

The reason for doing this is because it allows us to assume that each list is sorted, even though it has only one element in it.

I might have jumped a step in not clarifying that the recursive pattern would split the array first like this:

  1. [6, 1, 12] [2, 45, 7]
  2. [6, 1][12] [2, 45] [7]

Recursion would sort [6, 1] -> [1,6]

The Merge

Once all the elements are split into n sublists (our base case would be that the length of the subList is < 2), we would merge the sublists.

The Pseudocode

Using recursion is a difficult concept to understand. I know that when I first started it, I broke my browser with an infinite loop many times. But to start, we have a good base case here which is

Does the subarray have only 1 element in it?

Let’s start with some general concepts:

  1. Loop over the input array
  2. Find the middle
  3. Split the array into sublists until we reach the end
  4. Compare values
  5. Merge sorted values until no more sublists remain

So a general pattern of approach can be

// iterate over the input array

// is the beginning value of the array less than the end?

  // if yes? Divide the array in half into subarrays

    // does the subarray have only 1 element in it?

                                 // if yes? keep dividing

                               // compare the values and swap positions

             // if no? stop dividing and compare the values

// if no? swap the positions of the beginning and end of the     input array

// is the length of the array less than or equal to 1? (our base case)

  // if yes? return the array

  // if no? call the function recursively

The merging is what is accomplished recursively. When I refer to “swap positions”, I am referring to sorting.

A great code solution for Javascript specificity can be found here.

Happy Coding!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s