# Implementing Heap Sort in JavaScript

Last week I wrote about implementing a max heap in JavaScript, now we’re going to put that knowledge to the test and write a heap sort algorithm. Understanding the implementation, and time and space complexities of a max heap will make understanding the heap sort algorithm quite simple.

# Step by Step Example

## The Process

We know in a max heap, the largest element is stored at the root. So these will be the steps of heap sort:

- Move the element at index 0 to the end of the array
- Re-heapify the array, excluding the last element
- Continue this process of swapping and re-heapifying each time excluding the elements that you’ve moved to the end of the array

## Expected result

Sort in ascending order

Input: [4, 2, 5, 1, 3, 6]

Output: [1, 2, 3, 4, 5, 6]

## First Step

First we need to turn our array into a max heap.

Now that our array is a max heap, we need to start swapping elements.

First we will swap the element at index 0 and index 5.

So the array is now: [4, 3, 5, 1, 2, 6]

Then, we need to re-heapify all of the elements except for the one at index 5.

## Second Step

We need to swap the elements at index 0 and index 4 and then re-heapify again.

After swap: [2, 3, 4, 1, 5, 6]

Then, re-heapify…

## Third Step

We need to swap the element at index 0 with the element at index 4.

Array before re-heapifying: [1, 3, 2, 4, 5, 6]

After re-heapifying…

## Fourth Step

Swap array[0] and array[2]

[1, 2, 3, 4, 5, 6]

Re-heapify

## Final Steps

We have 2 elements that haven’t been sorted yet. We will swap the elements and then our array is in order.

# Code

I won’t spend too much time talking about functions that are based off of things I went over in my last blog post. The main difference is that these won’t be class methods, however the concepts behind them are the same.

A `swap`

function, as we will be doing a lot of swapping.

Now we will make a `heapify`

function. This will be the equivalent to the `heapifyDown`

method from my last blog.

One difference is we need to pass in a length property, as when we use this with our `heapSort`

function, we will be passing in the last index of the unsorted section of our array. We don’t want it to take the maximum value that we just put at the end of our array, and put it back at index 0. This is why our `if`

statements check to make sure the children aren’t beyond the `length`

.

Finally, our `heapSort`

function.

The code from lines 3 to 5, acts as our `buildHeap`

method from the last blog. From there it is just like the step by step example. Swapping the first element with the last element in the unsorted section, and then re-heapifying the unsorted section. It is similar to selection sort.

# Time Complexity, Space Complexity, and Stability

## Time Complexity

To analyze the time complexity of heap sort, we break down each step.

- Turn the array into a max heap
- Iterate through the array, on each iteration:

a. Swap elements

b. Re-heapify the array

From my last blog we know that to turn an array into a max heap takes O(n) time, and that `heapify`

takes O(log n) time. Swapping takes constant, or O(1) time.

So we have:

O(n) + O(n * (1 * log n))

We know we don’t care about constants, which then leaves us with:

O(n + n log n)

We only care about the dominant term of the function, so our **time complexity is O(n log n).**

## Space Complexity

We are sorting in place, so heap sort takes **O(1) space complexity.**

## Stability

**Heap sort is unstable.** If you need a reminder on what that means you can review my blog about implementing insertion sort in JavaScript, where I go over it in more detail.

# In Conclusion…

Heap sort isn’t see very often in the real world, but it could be useful for embedded systems where you’re working with little memory, because it takes O(1) space in memory. In addition to that, its best, worst, and average time complexity are all O(n log n), so you don’t run the risk of it taking O(n²) like with quick sort. However, heap sort isn’t as fast as quick sort on large arrays, and offers no advantage when handling partially/mostly sorted arrays. Introsort is a sorting algorithm which seeks to combine the advantages of quick sort and heap sort. The code used in this blog can be found in this GitHub repository.