How is Array#sort in Ruby so quick?
ruby, sorting
Solution
Array#sort is implemented in C, see `rb_ary_sort` in array.c
It also has some checks to compare Fixnums so sorting an array of Integers doesn't even need method lookups.
Problem
C# has BitArray, C has bit fields.. I couldn't find an equivalent in the Ruby core. Google showed me a `BitField` class that Peter Cooper has written for the same. I've been reading Jon Bentley's Programming Pearls and while trying out one of the first examples, which deals with a BitMap sort - I needed a type that is an array of bits. I used Peter's class ``` class BitMapSort def self.sort(list, value_range_max) bitmap = BitField.new(value_range_max) list.each{|x| bitmap[x] = 1 } sorted_list = [] 0.upto(value_range_max-1){ |number| sorted_list << number if (bitmap[number] == 1) } sorted_list end end ``` Running this on a set of 1M unique numbers in the range [0, 10,000,000), produced some interesting results, ``` user system total real bitmap 11.078000 0.015000 11.093000 ( 11.156250) ruby-system-sort 0.531000 0.000000 0.531000 ( 0.531250) quick-sort 21.562000 0.000000 21.562000 ( 21.625000) Benchmark.bm(20){|x| x.report("bitmap"){ ret = BitMapSort.sort(series, 10_000_000);} x.report("ruby-system-sort"){ ret = series.sort; } x.report("quick-sort"){ ret = QuickSort.sort( series, 0, series.length-1); } } ``` How is ruby's default sort 22x faster than 1M BitField.set + 1 loop over a 10M bit vector ? Is there a more efficient bit field / array in Ruby ? How does Ruby's default sort achieve this level of performance.. is it jumping into C to get this done?