Photo by Jan Antonin Kolar on Unsplash

In my last post, I have made an implementation of recursion in creating a palindrome. And in this post we will still apply that same process of recursion and then using another fundamental operation called merging.

Merge sort is one of the sorting algorithms and is based on the principle of divide and conquer.

It is a way of solving a problem by dividing it usually into two and then solving it individually, then finally those sub problems are merged into one final solution.

Let’s start by making a method called merge_sort.

def merge_sort(arr) end

This method will accept a non-sorted array of numbers. The first thing that we need to do is to declare a base case. Remember declaring a base case or an end goal is a condition that when is met, the function or method will stop calling itself recursively.

def merge_sort(arr) return arr if arr.size <= 1 end

In here we check the size or length of the array if it is less than or equals to 1, then we return it.

A one list is already sorted so if an array that only has one element we return that unaltered.

def merge_sort(arr) return arr if arr.size <= 1 left = merge_sort(arr[0...(arr.size/2)]) right = merge_sort(arr[arr.size/2..arr.size]) end

The next step is to use the recursion. We call our own method merge_sort.We will hold the first half of our array and assign it to a variable called left and the other half would go to the variable called right.

arr[0...(arr.size/2)] # the given array [4, 1, 3, 2, 6, 3, 18, 2, 9, 7, 3, 1, 2.5, -9] # will return this [4, 1, 3, 2, 6, 3, 18]

Given this snippet here, let’s say for example we have an array like this. [4, 1, 3, 2, 6, 3, 18, 2, 9, 7, 3, 1, 2.5, -9]

That will return [4, 1, 3, 2, 6, 3, 18] since it will be shown as arr(0...7)because arr.size/2 is equals to 7. And using ... means we’ll exclude the 7th index of the array so it’ll return the indices from 0 to 6 .The other half of the array applies the same concept.

def merge_sort(arr) return arr if arr.size <= 1 left = merge_sort(arr[0...(arr.size/2)]) right = merge_sort(arr[arr.size/2..arr.size]) merge(left, right) end

The last part uses another method called merge where it accepts the left and right variables that we created respectively.

In other languages like PHP, if we would like to return something we put the keyword ‘return’ explicitly. But in Ruby, devs usually leave it out, though can still use it if it’s not the last one in your method

Github Ruby Guideline

def merge(left, right) new_arr = [] new_arr << (left.first <= right.first ? left.shift : right.shift) while [left.size, right.size].min.positive? left.each { |i| new_arr << i } if left.size.positive? right.each { |i| new_arr << i } if right.size.positive? new_arr end

The method will return a newly sorted array so we need a storage for that.

We’ll need to check if the left and right contains at least one element. We do that by using the min and chaining it with the positive? method to check if the number is greater than 0. The loop will stop if either the left or right array returns 0 because positive? will return false.

Then we verify if the first element of the left part is lower than the first element of the right part, if it is, we shift the first element of the left array and add it to the new array. Otherwise we shift the right array’s first element.

Lastly, we check the remaining arrays by adding a condition that checks if the left or right arrays still contains elements, then we simply add it into the new array. Our last statement simply returns the newly sorted array.

def merge_sort(arr) return arr if arr.size <= 1 left = merge_sort(arr[0...(arr.size/2)]) right = merge_sort(arr[arr.size/2..arr.size]) merge(left, right) end def merge(left, right) new_arr = [] new_arr << (left.first <= right.first ? left.shift : right.shift) while [left.size, right.size].min.positive? left.each { |i| new_arr << i } if left.size.positive? right.each { |i| new_arr << i } if right.size.positive? new_arr end p merge_sort([4, 1, 3, 2, 6, 3, 18, 2, 9, 7, 3, 1, 2.5, 77, -9]) # [-9, 1, 1, 2, 2, 2.5, 3, 3, 3, 4, 6, 7, 9, 18, 77]

Here is the complete code and can be found in Github