Advanced Search

Iterative Merge Sort

/ Published in: Ruby
Save to your folder(s)
Originally written by Erik Kastner (@kastner).

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. # Erik Kastner 2008-02-13 iterative merge sort in ruby
  2. require 'rubygems'
  3. require 'activesupport'
  4.  
  5. # iterative merge sort. given [10,9,8,7,6,5,4,3,2,1], first loop would do
  6. # [10,9] => [9,10], [8,7] => [7,8]... etc second loop
  7. # [9,10,7,8] => [7,8,9,10]... etc
  8. def merge_sort(a)
  9.   # a one element array is already sorted
  10.   return a unless a.size > 1
  11.  
  12.   # first groups are like [[10], [9]]...
  13.   merge_size = 2
  14.  
  15.   # loop until merge_size > array.size
  16.   # you can also find the nearst power of 2, for 10 thats 16
  17.   # that's (log(a.size) / log(2))**2
  18.   loop do
  19.     offset = 0
  20.     a.in_groups_of(merge_size) do |sub_array|
  21.       subs = sub_array.in_groups_of(merge_size / 2)
  22.       sub_array.size.times do |i|
  23.         next if i+offset >= a.size
  24.  
  25.         # after the sub elemnts are shifted off, sub arrays might be empty
  26.         # or have nil elements
  27.         if (subs[0].empty? || subs[0].first.nil?)
  28.           a[i+offset] = subs[1].shift; next
  29.         end
  30.         if (subs[1].empty? || subs[1].first.nil?)
  31.           a[i+offset] = subs[0].shift; next
  32.         end
  33.  
  34.         # set a[i+offset] to the lesser of the first elements of the sub arrays
  35.         # shift that off the sub array
  36.         a[i+offset] = (subs[0].first < subs[1].first) ? subs[0].shift : subs[1].shift
  37.       end
  38.       offset += sub_array.size
  39.     end
  40.     break if merge_size > a.size
  41.     merge_size *= 2
  42.   end
  43.   a
  44. end
  45.  
  46. a = [10,9,8,7,6,5,4,3,2,1]
  47. # a = (1..8).map{rand(200)}
  48. puts "before: #{a.inspect}"
  49. puts "after: " + merge_sort(a).inspect

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

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.