Skip to content### Complexity

### Algorithm

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region. Unlike selection sort, heapsort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step.

Heap Sort has a *linearithmic* time complexity for most common cases.

Heap Sort performs (close to) *linear*, which is better than *linearithmic*, in one specific case: when the input list contains (large series of) identical numbers.

Below the implementation of Heap Sort as used on this page.

src/algorithms/heap-sort.ts

`1export default class HeapSort extends Algorithm {2 name = "Heap Sort"3 timeComplexityBest = Complexities.linearithmic4 timeComplexityAverage = Complexities.linearithmic5 timeComplexityWorst = Complexities.linearithmic67 execute(array: number[]): void {8 this.buildHeap(array)9 for (let i = array.length - 1; i > 0; i--) {10 this.swap(array, 0, i)11 this.heapify(array, 0, i)12 }13 }1415 buildHeap(array: number[]) {16 for (let i = Math.floor(array.length / 2); i >= 0; i--) {17 this.incrementOpCounter()18 this.heapify(array, i, array.length)19 }20 }2122 heapify(array: number[], i: number, length: number) {23 this.incrementOpCounter()24 const left = 2 * i + 125 const right = 2 * i + 226 let largest = i2728 if (left < length && array[left] > array[largest]) {29 largest = left30 }3132 if (right < length && array[right] > array[largest]) {33 largest = right34 }3536 if (largest !== i) {37 this.swap(array, i, largest)38 this.heapify(array, largest, length)39 }40 }4142 // eslint-disable-next-line class-methods-use-this43 swap(array: number[], i: number, j: number): void {44 const tmp = array[i]45 array[i] = array[j]46 array[j] = tmp47 }48}`