public
Created

merge sort

  • Download Gist
sort.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
def merge(list, low, mid, high)
aux = []
low.upto(high) do |copier_index|
aux[copier_index] = list[copier_index]
end
 
i = low
j = mid + 1
 
low.upto(high) do | index |
if i > mid
list[index] = aux[j]
j += 1
elsif j > high
list[index] = aux[i]
i += 1
elsif aux[j] < aux[i]
list[index] = aux[j]
j += 1
else
list[index] = aux[i]
i += 1
end
end
 
list
end
 
def merge_sort(list, low, high)
 
if high <= low
return
end
 
mid = low + (high - low) / 2
 
merge_sort(list, low, mid)
 
merge_sort(list, mid + 1, high)
 
merge(list, low, mid, high)
 
list
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.