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