## Posted By

jrphelps on 02/13/08

## Who likes this?

1 person have marked this snippet as a favorite

# Iterative Merge Sort

/ Published in: Ruby

Originally written by Erik Kastner (@kastner).

`# Erik Kastner 2008-02-13 iterative merge sort in rubyrequire '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]... etcdef 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  aend 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`