Rubyでクイックソート

require 'benchmark'

class Array
  def quicksort
    return self if self.size <= 1
    pivot = self[0]
    right = Array.new
    left = Array.new
    (1..self.size-1).each do |i|
      if self[i] <= pivot
        left.push(self[i])
      else
        right.push(self[i])
      end
    end
    left = left.quicksort
    right = right.quicksort
    return left + [pivot] + right
  end

  # もっとRubyっぽい書き方
  def quick_sort
    return self if self.length <= 1
    pivot = pop
    left, right = partition { |e| e < pivot }
    push pivot
    left.quick_sort + [pivot] + right.quick_sort
  end
end

sample = (0..10000).sort_by { rand }

puts Benchmark::CAPTION
puts Benchmark.measure { sample.quicksort }
puts Benchmark.measure { sample.quick_sort }
puts Benchmark.measure { sample.sort }

      user     system      total        real
  0.060000   0.000000   0.060000 (  0.058320)
  0.040000   0.000000   0.040000 (  0.045914)
  0.000000   0.000000   0.000000 (  0.001648)

Arrayに組み込んでみました。
quicksortが今回作成したものですが、
Enumerable#partitionを使うとよりRubyっぽくかけます。
(quick_sort)

Rubyでソート・アルゴリズムを表現しよう!

Array#sortの実装はこちら（C言語）
https://github.com/ruby/ruby/blob/trunk/array.c
(rb_ary_sort_bangメソッドで実装されているっぽい)

C言語難しくてよくわからないです(´・ω・`)