quicksort

class Array
  def quicksort(min=0, max=length-1)
    if min < max
      mid = partition(min, max)
      quicksort(min, mid - 1)
      quicksort(mid + 1, max)
    end
    self
  end

  def partition(min, max)
    pivot = self[max]
    border = min - 1
    (min..max-1).each do |j|
      if self[j] <= pivot
        border += 1
        self[border], self[j] = self[j], self[border]
      end
    end
    self[border+1], self[max] = self[max], self[border+1]
    border + 1 
  end
end