CodingReported in a candidate post, May 2024
Heap Sort Implementation
Filed under Microsoft · Also reported at Spotify
Free read 3 of 3Confirm 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
Confirm if sorting should be done in-place and whether ascending or descending is expected.
Repeatedly find the maximum element and move it to the end, similar to selection sort but using a heap structure.
Build a max-heap from the input array in O(N) time. Repeatedly extract the maximum element by swapping it with the last element and heapifying the reduced heap.
Empty array, single element array, or arrays with duplicate elements.
Solution
O(N log N) time, O(1) space
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.