4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.