Collapse Sort

Collapse_Sort.rb

require 'benchmark'
array = %w(
  18 5 11  67  55  16  63  15  35  97  9 7 40  42  14  98  50  94  16  86  34  2 39  12  43  42  49  77  48  85  94  57  59  65  96  2 85  59  5 35  28  17  68  55  43  43  73  68  97  79  84  58  34  83  16  7 67  79  24  76  53  43  8 55  56  91  4 44  61  86  73  14  42  60  61  33  58  37  96  73  4 31  8 17  27  60  33  77  6 98  71  12  73  75  97  4 7 83  30  54
).map! {|x| x.to_i}

def collapse_sort(array)
  sorted = []
  array.each do |item|
    if sorted[item]
      sorted[item].flatten! if sorted[item].class == Array
      sorted[item] = [sorted[item], item]
    else
      sorted[item] = item
    end  
  end
  sorted.compact.flatten
end

# p collapse_sort(array)

n = 1000
print "Collapse Sort: #{Benchmark.measure {n.times {collapse_sort(array)}}}"
print "Quick Sort:    #{Benchmark.measure {n.times {array.sort}}}"