Implement Heap Sort in ruby

min_heap_sort.rb

module MinHeapSortV1
  module_function

  def heap_sort(array)
    n = array.length
    a = [nil] + array

    (n / 2).downto(1) { |i| heapify(a, i, n) }

    while n > 1
      printf "#{a}\n"
      a[1], a[n] = a[n], a[1]
      n -= 1
      heapify(a, 1, n)
    end
    a.drop(1)
  end


  def heapify(array, parent, limit)
    root = array[parent]
    while (child = 2 * parent) <= limit
      child += 1 if child < limit && array[child] < array[child + 1]
      break if root >= array[child]

      array[parent], parent = array[child], child
      array[parent] = root
    end
  end

  def sort(arr)
    puts '------------------------------MIN HEAP SORT V1 O(nlogn)--------------------------'
    print heap_sort(arr)
    puts ''
  end
end

module MinHeapSort
  extend self

  @heap = Array.new
  @sorted = Array.new

  def create_heap(arr)
    arr.each_with_index { |num, index| insert(index, num) }
    @heap
  end

  def insert(index, node)
    @heap[index] = node
    bubble_up(index)
  end

  def bubble_up(index)
    parent_index = (index - 1) / 2
    child_index = index
    return if child_index.zero?

    if @heap[child_index] < @heap[parent_index]
      swap(parent_index, child_index)
      bubble_up(parent_index)
    end
  end

  def swap(parent_index, child_index)
    temp = @heap[child_index]
    @heap[child_index] = @heap[parent_index]
    @heap[parent_index] = temp
  end

  def extract_min
    while @heap.length > 0
      @sorted << @heap.first
      swap(0, @heap.length - 1)
      @heap.delete_at(@heap.length - 1)
      sink_down(0)
    end
    @sorted
  end

  def sink_down(parent_index)
    smallest_index = parent_index
    left_child = 2 * parent_index + 1
    right_child = 2 * parent_index + 2

    smallest_index = left_child if @heap[left_child] && @heap[left_child] < @heap[smallest_index]
    smallest_index = right_child if @heap[right_child] && @heap[right_child] < @heap[smallest_index]

    return if smallest_index == parent_index

    swap(parent_index, smallest_index)
    sink_down(smallest_index)
  end

  def sort(arr)
    puts '------------------------------MIN HEAP SORT O(nlogn)--------------------------'
    print create_heap(arr)
    puts ''
    print extract_min
    puts ''
  end
end

arr = [3,7,8,4,10,16,2,1,12]

MinHeapSortV1.sort(arr.dup)
MinHeapSort.sort(arr.dup)