Ruby Program for Merge Sort with Example and Explanation

A Ruby program for merge sort uses a recursive merge_sort method that splits the array, sorts each half, and merges them back with a merge helper; for example: def merge_sort(arr); return arr if arr.size <= 1; mid = arr.size / 2; left = merge_sort(arr[0...mid]); right = merge_sort(arr[mid..-1]); merge(left, right); end.

Examples

Input[3, 1, 4, 2]

Output[1, 2, 3, 4]

Input[10, 5, 2, 7, 3]

Output[2, 3, 5, 7, 10]

Input[]

Output[]

How to Think About It

To sort an array using merge sort, first split the array into two halves until each part has one or zero elements. Then, merge these small parts back together in sorted order by comparing their elements one by one. This way, the array becomes sorted step by step.

Algorithm

1

If the array has one or no elements, return it as it is already sorted.

2

Split the array into two halves.

3

Recursively apply merge sort to each half.

4

Merge the two sorted halves into one sorted array.

5

Return the merged sorted array.

Code

ruby

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

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

puts merge_sort([3, 1, 4, 2]).inspect

Output

[1, 2, 3, 4]

Dry Run

Let's trace [3, 1, 4, 2] through the merge sort code

1

Initial call

Array: [3, 1, 4, 2], split into [3, 1] and [4, 2]

2

Sort left half

Sort [3, 1]: split into [3] and [1], both single elements

3

Merge left half

Merge [3] and [1] into [1, 3]

4

Sort right half

Sort [4, 2]: split into [4] and [2], both single elements

5

Merge right half

Merge [4] and [2] into [2, 4]

6

Merge both halves

Merge [1, 3] and [2, 4] into [1, 2, 3, 4]

Step	Left Array	Right Array	Merged Result
1	[3, 1]	[4, 2]
2	[3]	[1]	[1, 3]
3	[4]	[2]	[2, 4]
4	[1, 3]	[2, 4]	[1, 2, 3, 4]

Why This Works

Step 1: Splitting the array

The code splits the array into halves recursively using arr[0...mid] and arr[mid..-1] until arrays have one or zero elements.

Step 2: Merging sorted halves

The merge method compares the first elements of each half and builds a new sorted array by picking the smaller element each time.

Step 3: Recursive sorting

By recursively sorting and merging, the entire array becomes sorted without needing to sort the whole array at once.

Alternative Approaches

Iterative Merge Sort

ruby

def merge_sort_iterative(arr)
  width = 1
  n = arr.size
  while width < n
    (0...n).step(width * 2) do |i|
      left = arr[i, width] || []
      right = arr[i + width, width] || []
      arr[i, left.size + right.size] = merge(left, right)
    end
    width *= 2
  end
  arr
end

puts merge_sort_iterative([3, 1, 4, 2]).inspect

Uses loops instead of recursion; can be more memory efficient but code is more complex.

Using Ruby's built-in sort

ruby

arr = [3, 1, 4, 2]
puts arr.sort.inspect

Simplest way to sort but does not teach merge sort algorithm.

Complexity: O(n log n) time, O(n) space

Time Complexity

Merge sort splits the array into halves recursively (log n splits) and merges all elements (n) at each level, resulting in O(n log n) time.

Space Complexity

It requires extra space to hold merged arrays during the merge steps, so space complexity is O(n).

Which Approach is Fastest?

Recursive merge sort is clear and efficient; iterative merge sort can save stack space but is more complex; built-in sort is fastest in practice but hides the algorithm.

Approach	Time	Space	Best For
Recursive Merge Sort	O(n log n)	O(n)	Learning and general sorting
Iterative Merge Sort	O(n log n)	O(n)	Memory-sensitive environments
Ruby Built-in Sort	O(n log n)	O(n)	Quick sorting without algorithm details