Heapsort algorithm
Filed under Microsoft
Free read 3 of 3Confirm if sorting must be in-place and whether auxiliary space is restricted.
The question
Implement the heapsort algorithm to sort an array of integers in ascending order in-place.
Constraints
- 1 <= nums.length <= 50000
- -10^5 <= nums[i] <= 10^5
Examples
- Input
- nums = [5,2,3,1]
- Output
- [1,2,3,5]
- Why
- The array is sorted in ascending order.
Approach
Confirm if sorting must be in-place and whether auxiliary space is restricted.
Use a min-heap by pushing all elements and popping them out, taking O(N log N) time and O(N) space.
Build a max-heap from the input array in-place. Repeatedly extract the maximum element by swapping it with the last element and heapifying the reduced heap.
Empty array, single-element array, and arrays with identical elements.
Tips
- What they are testing: Test already sorted arrays, reverse sorted arrays, and arrays with duplicate elements.
- Common mistake: Off-by-one errors when calculating child indices in 0-indexed arrays (left = 2*i + 1, right = 2*i + 2).
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.