Skip to content

Instantly share code, notes, and snippets.

@lysu
Created April 4, 2013 12:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lysu/5309982 to your computer and use it in GitHub Desktop.
Save lysu/5309982 to your computer and use it in GitHub Desktop.
merge sort
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment