← Microsoft questions
CodingReported in a candidate post, May 2024

Heap Sort Implementation

Filed under Microsoft · Also reported at Spotify

Free read 3 of 3

Confirm if sorting should be done in-place and whether ascending or descending is expected.

The question

Implement Heap Sort to sort an array of integers in ascending order.

Constraints

  • Must be implemented in-place without requiring O(N) extra space for sorting.
  • 1 <= nums.length <= 50000

Examples

Input
nums = [4, 10, 3, 5, 1]
Output
[1, 3, 4, 5, 10]
Why
The array is sorted in ascending order using a max-heap.

Approach

  1. Confirm if sorting should be done in-place and whether ascending or descending is expected.

Solution

O(N log N) time, O(1) space

Python
def heapSort(nums):
    def heapify(n, i):
        largest = i
        l, r = 2 * i + 1, 2 * i + 2
        if l < n and nums[l] > nums[largest]: largest = l
        if r < n and nums[r] > nums[largest]: largest = r
        if largest != i:
            nums[i], nums[largest] = nums[largest], nums[i]
            heapify(n, largest)
    n = len(nums)
    for i in range(n // 2 - 1, -1, -1): heapify(n, i)
    for i in range(n - 1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        heapify(i, 0)
    return nums

Tips

  • What they are testing: Test with already sorted arrays, reverse-sorted arrays, and arrays with negative numbers.
  • Common mistake: Off-by-one errors when calculating left and right child indices in 0-indexed arrays.

Related Microsoft questions

Collected from public candidate posts and coding forums. Updated Nov 2026.