Sorts

#!/usr/bin/env ruby

require 'benchmark'

class Array
  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

  def heap_sort!
    build_heap

    (size-1).downto(1) do |i|
      self[0], self[i] = self[i], self[0]
      heapify(0, i)
    end
  end

  def build_heap
    ((size-1)/2).downto(0) do |i|
      heapify(i)
    end
  end

  def heapify(index, heap_size = size)
    left  = heap_left_child_index(index)
    right = heap_right_child_index(index)

    largest = index
    largest = left  if left  < heap_size && self[left]  > self[largest]
    largest = right if right < heap_size && self[right] > self[largest]

    if largest != index
      self[largest], self[index] = self[index], self[largest]
      heapify(largest, heap_size)
    end
  end

  def heap_left_child_index(current_index)
    current_index * 2 + 1
  end

  def heap_right_child_index(current_index)
    current_index * 2 + 2
  end

  def merge_sort
    tmp = self.dup
    return tmp if tmp.length <= 1
    a, b = self.half.map { |e| e.merge_sort }
    merge(a, b)
  end
  def half
    mid = length/2
    return slice(0...mid), slice(mid..-1)
  end

  def merge(a, b)
    res = []
    until a.empty? && b.empty?
      res <<
      case
      when a.empty? then b.shift
      when b.empty? then a.shift
      when a.first < b.first then a.shift
      else b.shift
      end
    end
    res
  end
end

def nums
  n = []
  1000000.times { n << rand(1000000000) }
  n.uniq
end

n = nums

puts "Quick Sort: #{Benchmark.realtime { n.quick_sort } }"
puts "Merge Sort: #{Benchmark.realtime { n.merge_sort } }"
puts "Heap Sort:  #{Benchmark.realtime { n.heap_sort! } }"