class Allsorts
  def self.build_max_root_heap(arr)
    # build the arr to a heap with max root 
    return arr if arr.size <=1
    (1..(Math.log(arr.size,2).to_i)).to_a.reverse.each do |i|
      end_ ||= arr.size-1
      ((2**i-1)..end_).each do |j|
        if j % 2 == 0
          arr[j-1], arr[j] = arr[j], arr[j-1] if arr[j-1] < arr[j]
          arr[j/2-1], arr[j-1] = arr[j-1], arr[j/2-1] if arr[j/2-1]<arr[j-1]
        end
        if j == end_ and j % 2 !=0 
          arr[j/2], arr[j] = arr[j], arr[j/2] if arr[j/2] < arr[j]
        end
      end
    end
    arr
  end

  def self.heapsort(arr)
    return arr if arr.size <=1
    (arr.size - 1).times do |i|
      j = arr.size - i - 1
      arr[0..j] = self.build_max_root_heap(arr[0..j])
      arr[j], arr[0] = arr[0], arr[j]
    end
    arr
  end
end