Merge Sort in Ruby

Merge sort is one of the fundamental sorting algorithms used in computer science. It belongs to the divide and conquer category of algorithms, where a problem is divided into smaller sub-problems that are solved recursively. In this blog post, we’ll explore merge sort in-depth, focusing on its implementation in Ruby.

What is Merge Sort?

Merge sort operates by dividing an array into two halves, sorting each half separately, and then merging the sorted halves back together. It follows the divide and conquer strategy to efficiently sort large datasets.

The key steps of the merge sort algorithm can be summarized as follows:

Divide the unsorted array into two halves. Recursively sort each half. Merge the sorted halves back together. Ruby Implementation: Now, let’s delve into the implementation of merge sort in Ruby:

def merge_sort(arr)
  return arr if arr.length <= 1

  mid = arr.length / 2
  left_half = merge_sort(arr[0...mid])
  right_half = merge_sort(arr[mid..])

  merge(left_half, right_half)
end

def merge(left, right)
  sorted_arr = []
  until left.empty? || right.empty?
    if left.first <= right.first
      sorted_arr << left.shift
    else
      sorted_arr << right.shift
    end
  end
  sorted_arr + left + right
end

# Example usage:
arr = [3, 7, 2, 8, 1, 9, 5, 4, 6]
sorted_arr = merge_sort(arr)
puts sorted_arr.inspect

Here’s a breakdown of what each part of the code is doing:

The function merge_sort(arr) is the main function that implements the merge sort algorithm. It first checks if the array has a length of 1 or less. If it does, there’s no point in sorting it, so it returns the array. If the array has more than one element, it finds the midpoint of the array, splits the array into two halves at that point, and then recursively calls merge_sort on each half. The merge(left, right) function is handling the actual merging of the sorted sub arrays. It creates an empty array sorted_arr, and then in a loop, it continuously removes the smallest element from the first position of the left or right array and adds it to sorted_arr. This process continues until one of the arrays is empty. At the end, it concatenates any remaining elements from left or right to sorted_arr, and returns it. Finally, in the example usage, you create an array arr, call merge_sort(arr), and put the result in sorted_arr, which you then print.

Tags: Ruby