Recursive Ruby merge sort

Question

I have implemented a merge sort in Ruby. (Yes, I know, there's Array#sort) I would like to get feedback on code quality and optimization.

def merge(a, b)
  result = []

  while !a.empty? && !b.empty?
    if a[0] <= b[0]
      result << a.shift
    else
      result << b.shift
    end
  end

  result += a += b

  return result
end

def merge_sort(m)
  if m.length <= 1
    return m
  end

  left, right = [], []
  m.each_with_index do |x, i|
    if i < m.length / 2
      left << x
    else
      right << x
    end
  end
  left = merge_sort(left)
  right = merge_sort(right)

  return merge(left, right)
end

input = [*1..100].shuffle

p input

p merge_sort input

Eric Duminil · Accepted Answer · 2017-12-16 14:29:47Z

You can define left and right in merge_sort this way:

n = m.length
if n <= 1
  return m
end

left = merge_sort(m[0 ... n/2])
right = merge_sort(m[n/2 .. -1])

Depending on your Ruby version, Array#shift can be O(n). You could keep 2 indices for a and b:

def merge(a, b)
  result = []
  i, j = 0, 0
  na, nb = a.size, b.size

  while i < na && j < nb do
    if a[i] <= b[j]
      result << a[i]
      i += 1
    else
      result << b[j]
      j += 1
    end
  end

  return result + a[i..-1] + b[j..-1]
end

With those changes, the code becomes twice as fast with input = [*1..100000].shuffle.

Stack Exchange Network

Recursive Ruby merge sort

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Recursive Ruby merge sort

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions