JavaScript Array Sort Algorithms: A Tutorial for Coding Interviews

Sorting lists of data is such a crucial part of processing in applications.

It is useful for displaying data and performing searches. It is, therefore, no surprise that any good software engineer should know how to sort arrays. This article explains some of the most common algorithms for sorting arrays in JavaScript.

What Is Sorting, and Why Is It Useful?

Sorting is the systematic organization of values by some order. This order could be descending or ascending. Sorting arrays in JavaScript is useful as it enables data to be displayed more meaningfully.

For example, a person may wish to see files sorted with the most recent files first or products sorted by price. It is also useful for performing binary search on data, which only works with sorted data.

While there are functions and libraries to help you sort data easily, you still need to know how sorting works under the hood for coding interviews or when you have to write low-level code.

JavaScript Array Sort Algorithms

Bubble Sort

Bubble Sort is arguably the easiest algorithm to understand and implement. It works by looping through the array in a pass. With each pass, we move through the array, from start to end, comparing two adjacent elements. If the elements are in the wrong order, we swap them.

We perform n passes where n is the number of elements in the array. With each pass, the array is sorted starting from the right. The pseudocode for the algorithm to sort numbers in ascending order is as follows:

1. Let n be the number of elements in the array
2. Loop n times, keeping count of the loops using i (doing the following in each loop)
   a. loop the array from the second element to the (n - i)th element
   b. if the previous element is greater than the current element, swap them.

Translating it to JavaScript, the code would look like this:

function sort(arr) {
    const n = arr.length;

    for (let i = 0; i < n; i  ) {
        for (let j = 1; j  arr[j]) {
                const temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    
    return arr;
}

To better understand what is happening, I’d recommend adding a console.logs inside the two loops to see how the array changes with each pass.

In the code below, I have modified the sort function to add console.logs inside the two loops. I have also created a small unsorted array that I sorted using the sort function.

function sort(arr) {
    const n = arr.length;

    for (let i = 0; i < n; i  ) {
	console.log(`Pass: ${i}`);

        for (let j = 1; j  arr[j]) {
                const temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
	
	    console.log(arr);
        }
    }
    
    return arr;
}

const array = [9, 2, 7, 4, 1];
sort(array);

console.log(array);

The result of running the above code would be:

Bubble sort has a Big O time complexity of O(n ^ 2). This is because it performs n passes, which loops through the array for each pass. Therefore, it does not scale well. However, it has a space complexity of O(1) since it modifies the array elements in place.

Insertion Sort

Insertion sort is a popular JavaScript array sort algorithm. Suppose we are using insertion sort to sort values in ascending order. The algorithm works by picking a number, which we will call num. It then moves num left until every other number to the left of num is smaller than num. All numbers will be sorted if this is done from the second element until the end. Here’s a description in pseudocode.

1. Let n be the number of elements in the array
2. Loop i from 1 to n - 1 (start from the second element)
    a. Set currentElement to array[i]
    b. Set j to i - 1
    c. While j >= 0 and array[j] > current_element
       i. Move array[j] to array[j 1]
       ii. Decrement j by 1
    d. Set array[j 1] to current_element

And now, the pseudocode implemented in JavaScript is as follows.

function insertionSort(array) {
  const n = array.length;

  for (let i = 1; i = 0 && array[j] > currentElement) {
      array[j   1] = array[j];
      j -= 1;
    }

    array[j   1] = currentElement;
  }

  return array;
}

As with Bubble Sort, adding console.logs helps you visualize what is happening. The code snippet below shows you Insertion Sort at work.

function sort(array) {
    const n = array.length;

    for (let i = 1; i = 0 && array[j] > currentElement) {
            array[j   1] = array[j];
            j -= 1;
        }

        array[j   1] = currentElement;
        console.log("Placed it at position:", j   1);
        console.log(array);
    }

    return array;
}

const array = [4, 1, 2, 5, 3];
sort(array);

And running the snippet above yields the following result:

Merge Sort

While Insertion Sort and Bubble Sort scale in quadratic time, Merge Sort scales in quasi-linear time. It has a time complexity of O(n * log(n)).

Merge sort utilizes the divide and conquer strategy. The array is repeatedly divided into smaller arrays of 1 element each. After the division, they are then merged back.

The division is recursive so that the array can be reassembled afterward.

When merging the array back, the subarrays are merged in order. The merging is done in the same way that you would merge a sorted array. The pseudocode for doing so is written below:

1. If the length of the array is 1 or less, return the array (base case)
2. Find the middle index:
   a. Set mid to the floor of (length of the array / 2)
3. Divide the array into two subarrays:
   a. Create leftArray and copy the first half of the array into it (from index 0 to mid)
   b. Create rightArray and copy the second half of the array into it (from index mid 1 to the end)
4. Recursively call MergeSort on leftArray
5. Recursively call MergeSort on rightArray
6. Merge the two sorted subarrays:
   a. Create an empty resultArray
   b. While both leftArray and rightArray are not empty:
      i. If the first element in leftArray is less than or equal to the first element in rightArray, append it to resultArray
      ii. Otherwise, append the first element in rightArray to resultArray
   c. Append any remaining elements in leftArray to resultArray (if any)
   d. Append any remaining elements in rightArray to resultArray (if any)
7. Return resultArray

Implementing it in JavaScript would yield the following:

function sort(array) {

	// Base case in which we stop subdividing the array
	if (array.length == 1) {
		return array;
	}

	// Finding the middle point of the array
	const m = Math.round(array.length / 2);

	// Divide the array into two halves
	const leftUnsorted = array.slice(0, m);
	const rightUnsorted = array.slice(m);

	// Recursively call merge sort
	const leftSorted = sort(leftUnsorted);
	const rightSorted = sort(rightUnsorted);

	// Return a merged sorted array
	return merge(leftSorted, rightSorted);
}

function merge(left, right) {
	// Merge two sorted lists
	let result = [];
	let leftIndex = 0;
	let rightIndex = 0;

	while (leftIndex < left.length && rightIndex < right.length) {
		if (left[leftIndex] < right[rightIndex]) {
			result.push(left[leftIndex]);
			leftIndex  = 1;
		} else {
			result.push(right[rightIndex]);
			rightIndex  = 1;
		}
	}

	return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

If you run the code with an example array, it should work.

Quick Sort

Like Merge Sort, Quick Sort relies on the divide-and-conquer strategy. The algorithm selects a pivot element. Next, it moves all elements larger than the pivot to its right and smaller than the pivot to its left. Once this is done, the pivot will be in the correct position.

To move elements around the pivot, the algorithm starts by moving the pivot to the end of the array.

After moving it, we use a pointer to loop from the array’s left, looking for the first number greater than the pivot. Simultaneously, we use another pointer loop from the array’s right, looking for the first number lesser than the pivot. Once both numbers have been identified, we swap them. This procedure is repeated until the pointer from the left is greater than the pointer to the right.

When we stop, we swap the greater of the two numbers last swapped with the pivot. At this point, the pivot will be in the correct position; numbers less than the pivot will be to the left, while those greater will be to the right.

This procedure is repeated recursively for the sub-arrays to the left and right of the pivot until the subarrays have only one element left.

Here’s the pseudocode for quick sort:

1. If lessThanPointer is less than greaterThanPointer:
    a. Choose a pivot element from the array
    b. Move elements such that elements less are to the left and elements greater are to the right:
    c. Recursively call Quicksort on leftSubarray
    d. Recursively call Quicksort on rightSubarray

And converting it to JavaScript:

function sort(array, low, high) {
    if (low < high) {
        // Choose the pivot index and partition the array
        const pivotIndex = move(array, low, high);

        // Recursively sort the subarrays to the left and right of the pivot
        sort(array, low, pivotIndex - 1);
        sort(array, pivotIndex   1, high);
    }
}

function move(array, low, high) {
    // Select the pivot element (in this case, the last element)
    const pivotElement = array[high];

    // Initialize the index for the smaller element
    let i = low - 1;

    for (let j = low; j < high; j  ) {
        // If the current element is less than or equal to the pivot, swap it with the element at index i 1
        if (array[j] <= pivotElement) {
            i  = 1;
            const temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }

    // Swap the pivot element into its correct position
    const temp = array[i];
    array[i] = array[j];
    array[j] = temp;

    // Return the index of the pivot element
    return i   1;
}

Sorting an example array with Quick Sort in Node.js should yield the following:

In the best case, Quicksort runs in quasi-linear time complexity. Space usage in Quick Sort also scales logarithmically. Therefore, it is relatively efficient compared to other JavaScript array sort algorithms.

Tips for Your Coding Interviews

❇️ Practice is key. It helps you learn different algorithms, but more importantly, it helps you develop problem-solving and computational thinking skills. You can also practice on platforms like Leetcode and AlgoExpert.

❇️ Try to solve the problem first. Instead of jumping straight to the solution, try to solve it, as it helps you develop your problem-solving skills.

❇️ If a problem is taking too long, jump to the solution; you can still learn to solve the problem from the solution. Most platforms for learning offer solutions. ChatGPT or Google Bard are also useful for explaining concepts.

❇️ Also, don’t write code immediately; whiteboard your solutions and think them through before writing code. Pseudocode is also a useful way of writing down ideas quickly.

Conclusion

In this article, we covered the most popular sorting algorithms. However, learning all this may seem overwhelming at first. Therefore, I usually recommend mixing various sources instead of just relying on one. Happy Coding!

Next, check out understanding sorted function in Python.