sort.rb

class Array
  def quick_sort
    n = self.size
    return self if n <= 1

    pivot = self.last
    less, more = [], []
    for i in 0...n-1
      item = self[i]
      if item < pivot
        less << item
      else
        more << item
      end
    end

    less.quick_sort + [pivot] + more.quick_sort
  end

  def merge_sort
    n = self.size
    return self if n <= 1

    mid = n/2
    left, right = self[0...mid], self[mid..-1]
    left, right = left.merge_sort, right.merge_sort

    result = []
    left_size, right_size = left.size, right.size
    while left_size > 0 || right_size > 0
      if left_size > 0 && right_size > 0
        if left.first > right.first
          result << right.first
          right = right[1..-1]
          right_size -= 1
        else
          result << left.first
          left = left[1..-1]
          left_size -= 1
        end

      elsif left_size > 0
        result << left.first
        left = left[1..-1]
        left_size -= 1

      elsif right_size > 0
        result << right.first
        right = right[1..-1]
        right_size -= 1
      end
    end

    result
  end
end

p [3,2,4,5,6].merge_sort
p [8,5,3,5,2].quick_sort