Advanced Search

Return to Snippet

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