Merge Sort in Ruby

Question

Can anybody please tell what am I doing wrong in my Merge-Sort

def print_array(a)
  print a
  print "\n\n"
end

#Merge-Sort code starts Here.
def merge_sort(a)
  if a.size < 2
    return a
  end

  middle = (a.length / 2).to_i
  left = a.slice(0, middle)
  right = a.slice(middle, a.size)

  merge_sort(left)
  merge_sort(right)

  a = merge(left, right)
end

def merge(left, right) 
  result = []

  while left.length > 0 || right.length > 0
    if left.length > 0 && right.length > 0
      if left[0] <= right[0]
        result << left.slice!(0)
      else
        result << right.slice!(0)
      end
    elsif left.length > 0
      result.concat left.slice!(0..left.length-1)
    elsif right.length > 0
      result.concat right.slice!(0..right.length-1)
    end
  end

  result  
end

a = [ 3, 2, 1 ]
print_array(a)

a = merge_sort(a)
print_array(a)

Basically, What I know is that when it comes time to Merge [2] and [1], that happens correctly (ie. [1, 2] is returned) , but for the previous step of the Recursion as it unwinds, it comes back (or doesn't come back) as [1, 2] but as [2, 1], ie.

Previous step -> left = [3] -> right = [2, 1] #This is the value of right from recursion instead of [1, 2]

I don't know how to fix this, and it's driving me crazy, Can you please help me?

Answer 1

These two lines:

merge_sort(left) 
merge_sort(right)

should be:

left = merge_sort(left) 
right = merge_sort(right)

Since your merge sort is not sorting in place, you need to assign the result back to the variables.