Common Sorting Algorithms in JavaScript

In this article, I will cover some common sorting algorithms in computer science. Sorting algorithms are important to study because they can often reduce the complexity of a problem. They also have direct applications in searching algorithms, database algorithms, and much more.

Sorting algorithms we will learn about:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Bucket Sort

Helper Methods for Swapping and Comparing

We will be swapping elements in arrays a lot so let's start by writing a helper method called swap:

function swap(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

We will be comparing elements a lot so I think it's a good idea to write a function for just that:

const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
};

function defaultCompare(a, b) {
    if (a === b) {
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

Okay, now that that's settled, let's move onto sorting!

Bubble Sort

Best: O(N), Worst: O(N^2)

The bubble sort is a good starting point since it is one of the simplest sorting algorithms. It's mostly just good for teaching purposes though since it is one of the slowest sorting algorithms.

In short, the bubble sort algorithm compares every two adjacent values and swaps them if the first one is bigger than the second one. This reflects its name since the values tend to move up into the correct order, like bubbles rising to the surface.

function bubbleSort(arr, compare = defaultCompare) {
    const { length } = arr;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) { // refer to note below
            if (compare(arr[j], arr[j + 1]) === Compare.BIGGER_THAN) {
                swap(arr, j, j + 1);
            }
        }
    }
    return arr;
}

Note that the solution I provided is a slightly improved version of the usual bubble sort algorithm since we are subtracting the number of passes from the inner loop to avoid unnecessary comparisons. To get a better understanding of what's actually happening, here is a diagram with an example:

Selection Sort

Best/Worst: O(N^2)

The basic idea behind the selection sort algorithm is that is finds the minimum value in the data structure, places it in the first position, finds the second minimum value, places it in the second position, and so on.

function selectionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let minIndex;
    for (let i = 0; i < length - 1; i++) {
        minIndex = i;
        for (let j = i; j < length; j++) {
            if (compare(arr[minIndex], arr[j]) === Compare.BIGGER_THAN) {
                minIndex = j;
            }
        }
        if (i !== minIndex) {
            swap(arr, i, minIndex);
        }
    }
    return arr;
}

The following diagram acts as an example of the selection sort algorithm in action:

Insertion Sort

Best: O(N), Worst: O(N^2)

The insertion sort algorithm builds the final sorted array one value at a time. The process looks something like this:

1. Assume the first element is already sorted.
2. Compare the first and second elements - should the second value stay in its place or be inserted before the first value?
3. Next, you can do a similar comparison with the third value - should it be inserted in the first, second, or third position? And so on...

function insertionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let temp;
    for (let i = 1; i < length; i++) {
        let j = i;
        temp = arr[i];
        while (j > 0 && compare(arr[j - 1], temp) === Compare.BIGGER_THAN) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
    return arr;
}

Refer to this diagram for an example of insertion sort in action:

The insertion sort algorithm has a better performance than the selection and bubble sort algorithms when sorting small arrays though again, I wouldn't really recommend using it outside educational purposes.

Merge Sort

Best/Worst: O(N Log N)

The merge sort algorithm is a divide-and-conquer algorithm. In other words, it divides the original array into smaller arrays until each small array has only one position, then it merges the smaller arrays into a bigger one that is sorted.

The implementation here is recursive and consists of two functions, one to divide the arrays into smaller ones and one to perform the sort:

function mergeSort(arr, compare = defaultCompare) {
    if (arr.length > 1) {
        const { length } = arr;
        const middle = Math.floor(length / 2);
        const left = mergeSort(arr.slice(0, middle), compare);
        const right = mergeSort(arr.slice(middle, length), compare);
        arr = merge(left, right, compare);
    }
    return arr;
}

function merge(left, right, compare) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(compare(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

Here's a diagram to visualize the process:

Quick Sort

Best/Average: O(N Log N), Worst: O(N^2)

The quick sort is one of the most used sorting algorithm. Similar to the merge sort, the quick sort also uses the divide-and-conquer approach. Let's break the process down into steps to understand it a little better since it's a bit more complex than the previous sorts we've covered:

1. Select a value from the array that we will call pivot, generally the value at the middle of the array.
2. Perform the partition operation which will result in an array with values lesser than the pivot on the left and greater on the right.
3. Repeat the first two steps for each subarray (left and right) until the arrays are completely sorted.

function quickSort(arr, compare = defaultCompare) {
    return quick(arr, 0, arr.length - 1, compare);
}

function quick(arr, left, right, compare) {
    let i;
    if (arr.length > 1) {
        i = partition(arr, left, right, compare);
        if (left < i - 1) {
            quick(arr, left, i - 1, compare);
        }
        if (i < right) {
            quick(arr, i, right, compare);
        }
    }
    return arr;
}

function partition(arr, left, right, compare) {
    const pivot = arr[Math.floor((right, left) / 2)];
    let i = left;
    let j = right;

    while (i <= j) {
        while (compare(arr[i], pivot) === Compare.LESS_THAN) {
            i++;
        }
        while (compare(arr[j], pivot) === Compare.BIGGER_THAN) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    return i;
}

Bucket Sort

Best/Average: O(N + k), Worst: O(N^2)

The bucket sort algorithm is a distributed sorting algorithm that separates the elements into different buckets, or smaller arrays, and then uses a simpler sorting algorithm good for sorting small arrays, such as insertion sort, to sort each bucket.

function bucketSort(arr, bucketSize) {
    if (arr.length < 2) {
        return arr;
    }
    // create buckets and distribute the elements
    const buckets = createBuckets(arr, bucketSize);
    // sort the buckets using insertion sort and add all bucket elements to sorted result 
    return sortBuckets(buckets);
}

function createBuckets(arr, bucketSize) {
    // determine the bucket count
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;

    // initialize each bucket (a multidimensional array)
    const buckets = [];
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }

    // distribute elements into buckets
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
        buckets[bucketIndex].push(arr[i]);
    }
    return buckets;
}

function sortBuckets(buckets) {
    const sortedArr = [];
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            insertionSort(buckets[i]); // quick sort is another good option
            sortedArr.push(...buckets[i]);
        }
    }
    return sortedArr;
}

Note that the bucket sort works best when the elements can be distributed into buckets evenly. If the elements are largely sparse, then using more buckets is better, and vice versa.

The following diagram demonstrates the bucket sort algorithm in action:

Conclusion

We have covered some of the most common sorting algorithms. There are a lot more sorting algorithms I didn't get to go over in this article so let me know if you would like me to write a second part. Either way, I plan to write about searching algorithms soon so stay tuned!

Below are some reference material (the sound of sorting video is my favorite!):

• Big O Notation Cheat Sheet
• The Sound of Sorting (Full Video) by Timo Bingmann
• Implementations in multiple languages from freeCodeCamp
• Sorting Visualization Tool from Visualgo
• Comedic Sorting Algo Webcomic from xkcd

Comments

[Functional Javascript]

Excellent work Christina.
You're an expert of sorts. ;)

I perf-tested all of them.
The quickSort throws even on quite small arrays due to the stackoverflow recursion

The fastest is the merge sort, in the 1-2 second range for an array of 1M numbers.

[Christina]

First of all, good one 😂

Second, thanks for double checking and good to know about your findings! Did you test it in codepen by chance?

[Functional Javascript]

I perf-tested these locally.

An example usage per func...

//@perftests
const aNums = genRandNums(1, 1e4, 1e6);
timeInLoop("mergeSort", 1, () => mergeSort(aNums));

genRandNums Source Code

gist.github.com/funfunction/f7adf6...

timeInLoop Source Code

gist.github.com/funfunction/91b587...

[Christina]

Oh this is awesome, thanks for sharing!

[edh_developer]

Heapsort would be a good one to cover.

A few reasons:

• heapsort is a good example of a pretty fast in-place algorithm
• heaps are just generally good things to be aware of
• heaps are relevant to improving the performance of mergesort, when you're doing a k-way merge with a large set of data

[Christina]

Good points! I'm considering writing another post as sort of a second part to this one and would likely include heap sort, counting sort, and radix sort... Thanks for the input, definitely makes me even more excited to continue learning about sorting algorithms!

[Dolores Greatamsky]

The merge step of MergeSort comes in handy when needing to merge any number of already sorted sequences into one sorted sequence. I recently used it to merge hundreds of "sorted string table"-style files into one larger file, where the result wouldn't have fit in main memory. Remembering about MergeSort really helped me there 😁

[Christina]

Wow, that's a really cool use of the merge process, good thinking!

[David]

Wow! You just keep firing! Nice work! I honestly don’t know the implementation for the slower sorts off the top of my head. What typically come to mind are O(n log n) sorting algos like quicksort, mergesort, and heapsort. Heap-sort has a lot of utility particularly on non-fixed size inputs (streams).

One note: I noticed that your merge function for mergesort could be improved — by not allocating a new array each time. The canonical implementation passes in the original array and replaces the elements in the original input array utilizing a third pointer within merge — this third pointer moves forward after a replacement and only one of the two pointers pointing at the smaller element of the two arrays being merged moves forward in each iteration. This halves the memory footprint of the current implementation.

[Andrew Eastwood]

It seems that we need i + 1 < right at the quickSort example.

[Polarisiota]

Excellent!