class Array
  def insert_sort
    array = self
    result = [self[0]]
    (1 .. (array.size - 1)).each do |e|
      result.insert_olderly!(array[e])
    end
    result
  end

  protected
  def insert_olderly!(k)
    self.replace(insert_olderly(k))
  end

  def insert_olderly(k)
    array = self
    result = []
    (0 .. (array.size - 1)).each do |i|
      if array[i] > k
        result << k
        result = result + array[i .. array.size-1]
        break
      else
        result << array[i]
        result << k if (i == array.size - 1)
      end
    end
    result
  end
end

class Array
  def merge_sort
    array = self
    if array.size > 2
      a1 = array.first_half.merge_sort
      a2 = array.last_half.merge_sort
      a1.merge_with_order(a2)
    elsif array.size == 2
      if array.first < array.last
        array
      else
        array.reverse
      end
    else
      array
    end
  end

  protected
  def merge_with_order(array)
    array_1 = self
    array_2 = array
    result = []
    size = array_1.size + array_2.size
    size.times do
      if array_1.first < array_2.first
        result << array_1.delete_at(0)
      else
        result << array_2.delete_at(0)
      end
      if array_1.size == 0
        result += array_2
        break
      end
      if array_2.size == 0
        result += array_1
        break
      end
    end
    result
  end

  def first_half
    self[0, self.size/2]
  end

  def last_half
    self[self.size/2, self.size]
  end
end

class Array
  def quick_sort
    return self if self.size <= 1
    left = []
    right = []
    pivots = []
    pivot = self.sample
    self.each do |e|
      if e < pivot
        left << e
      elsif e > pivot
        right << e
      else
        pivots << e
      end
    end
    return (left.quick_sort + pivots + right.quick_sort)
  end
end