Revision: 5130
at February 13, 2008 10:19 by jrphelps

Initial Code
```# Erik Kastner 2008-02-13 iterative merge sort in ruby
require 'rubygems'
require 'activesupport'

# iterative merge sort. given [10,9,8,7,6,5,4,3,2,1], first loop would do
# [10,9] => [9,10], [8,7] => [7,8]... etc second loop
# [9,10,7,8] => [7,8,9,10]... etc
def merge_sort(a)
# a one element array is already sorted
return a unless a.size > 1

# first groups are like [[10], [9]]...
merge_size = 2

# loop until merge_size > array.size
# you can also find the nearst power of 2, for 10 thats 16
# that's (log(a.size) / log(2))**2
loop do
offset = 0
a.in_groups_of(merge_size) do |sub_array|
subs = sub_array.in_groups_of(merge_size / 2)
sub_array.size.times do |i|
next if i+offset >= a.size

# after the sub elemnts are shifted off, sub arrays might be empty
# or have nil elements
if (subs[0].empty? || subs[0].first.nil?)
a[i+offset] = subs[1].shift; next
end
if (subs[1].empty? || subs[1].first.nil?)
a[i+offset] = subs[0].shift; next
end

# set a[i+offset] to the lesser of the first elements of the sub arrays
# shift that off the sub array
a[i+offset] = (subs[0].first < subs[1].first) ? subs[0].shift : subs[1].shift
end
offset += sub_array.size
end
break if merge_size > a.size
merge_size *= 2
end
a
end

a = [10,9,8,7,6,5,4,3,2,1]
# a = (1..8).map{rand(200)}
puts "before: #{a.inspect}"
puts "after: " + merge_sort(a).inspect```

Initial URL
`http://pastie.textmate.org/151527`

Initial Description
`Originally written by Erik Kastner (@kastner).`

Initial Title
`Iterative Merge Sort`

Initial Tags
`sort`

Initial Language
`Ruby`