Merge Sort

Merge Sort

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

#puts (0..arr.length/2-1)  # Left List
#puts (arr.length/2..arr.length-1) #Right List

leftarray = arr[0..arr.length/2-1]
rightarray = arr[arr.length/2..arr.length-1]
#middle = arr[arr.length/2-1]
#arr.each {|value| value < middle ? leftarray << value : rightarray << value}
#

leftarray = mergsort(leftarray)
rightarray = mergsort(rightarray)
return merge(leftarray,rightarray)
end

def merge(left,right)
  result = []

  while left.length != 0 and right.length != 0
    if left.first <= right.first
      result << left.first
      left.delete_at(0)
    else
      result << right.first
      right.delete_at(0)
    end

  end

  while left.length != 0 
      result << left.first
      left.delete_at(0)
  end
  while right.length != 0 
      result << right.first
      right.delete_at(0)
  end



return result
end

array = (1..10000).map { rand }
require 'benchmark'
Benchmark.bm do |x|
  x.report("Merge Sort") {mergsort(array)}
  x.report("Ruby") {array.dup.sort!}
end
puts mergsort(array).first
puts array.sort.first
puts mergsort(array).last
puts array.sort.last