Iterative Merge Sort


/ Published in: Ruby
Save to your folder(s)

Originally written by Erik Kastner (@kastner).


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.