Skip to content

Instantly share code, notes, and snippets.

@andersonvom
Created March 29, 2012 19:40
Show Gist options
  • Save andersonvom/2242877 to your computer and use it in GitHub Desktop.
Save andersonvom/2242877 to your computer and use it in GitHub Desktop.
Merge Sort
andersonvom /tmp/sort $ wc -l random.txt
1241894 random.txt
andersonvom /tmp/sort $ time ruby merge_sort.rb
real 0m21.932s
user 0m21.730s
sys 0m0.200s
input = "random.txt"
output = "ordered.txt"
numbers = []
def merge_sort(arr)
size = arr.size
return arr if size <= 1
if size == 2
return arr if (arr[0] <=> arr[1]) < 1
return arr.reverse
end
half = size / 2
arr1 = merge_sort arr[0..half]
arr2 = merge_sort arr[(half+1)..-1]
arr_sort = []
e1 = arr1.shift
e2 = arr2.shift
while (e1 and e2)
if (e1<=>e2) < 1
arr_sort << e1
e1 = arr1.shift
else
arr_sort << e2
e2 = arr2.shift
end
end
arr_sort << (e1 || e2)
arr_sort += arr1
arr_sort += arr2
end
if __FILE__ == $0
File.open(input, 'r') do |f|
while (line = f.gets)
numbers << line
end
end
output_numbers = merge_sort numbers
File.open(output, 'w') do |f|
f.write(output_numbers)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment