Implementation and Visualization of Merge Sort in Ruby

Leonora Squires

Feb 24·2 min read

Time to divide and conquer!…then put back together again!

Alright, let’s jump right into it.

Merge Sort

Merge sort is a rather efficient sorting algorithm that, once you get the hang of, will definitely come in handy while on your CS journey.

Much like quick sort, merge sort takes a kind of a “divide and conquer” approach. With merge sort, you split the array in half over and over again recursively until each element is by itself. Then each element is compared and merged back in order until all the elements are completely sorted.

Here’s a gif to give you an idea of what’s happening here.

And here’s a piece of code showing one of the ways we can implement merge sort using Ruby.

Code Breakdown

Sort Function (lines 3–19)

1. If the array is empty, or has only one element, return the array (lines 6–8)
2. Split the array in half and place them into two subarrays called left and right (lines 10–13)
3. Call the sort function on the left and right subarrays to continue to split each array until they are individual elements and place them into the sorted_left, and sorted_right arrays (lines 15–16)
4. Call the merge function on both the sorted_left and sorted_right arrays (line 18)

Merge Function (lines 21–40)

1. If the right_array is empty, return the left_array. If the left_array is empty, return the right_array (lines 23–29)
2. Compare the first value in both subarrays, and shift the smallest value into smallest_number (lines 31–35)
3. Recursively call the merge function on the subarrays until all of the elements are sorted and hold it in recursion (line 37)
4. Put smallest_number and the recursion array together and return your fully sorted array (line 39)

This may take some time for you to grasp, so don’t get discourage if you don’t understand it right away. Play around with the code, and with a bit more practice, you’ll have merge sort down in no time.