text: # Implementation of heap sort algorithm
  
  def heapify(nums, heap_size, root_index):
      # Assume the index of the largest element is the root index
      largest = root_index
      left_child = (2 * root_index) + 1
      right_child = (2 * root_index) + 2
  
      # If the left child of the root is a valid index, and the element is greater than
      # the current largest element, then update the largest element
      if left_child < heap_size and nums[left_child] > nums[largest]:
          largest = left_child
  
      # Do the same for the right child of the root
      if right_child < heap_size and nums[right_child] > nums[largest]:
          largest = right_child
  
      # IF the largest element is no longer the root element, swap them
      if largest != root_index:
          nums[root_index], nums[largest] = nums[largest], nums[root_index]
  
          # Heapify the new root element to ensure it's the largest
          heapify(nums, heap_size, largest)
  
  def heap_sort(nums):
      n = len(nums)
  
      # Create a max heap for the list
      # The second argument of the range means we stop at the element before -1 i.e.
      # the first element of the list.
      # The third argument of the range means we irerate backwards, reducing the count of i by 1
  
      for i in range(n, -1, -1):
          heapify(nums, n, i)
  
      # Move the root of the max heap to the end of
      for i in range(n - 1, 0, -1):
          nums[i], nums[0] = nums[0], nums[i]
          heapify(nums, i, 0)
  
  # Verify it works
  random_list_of_nums = [12, 59, 4, 1, 98, 45, 49, 25]
  heap_sort(random_list_of_nums)
  print(random_list_of_nums)