Problem
I’m practicing js, unit testing, and algorithms, so implementing some of the common sorting algorithms and doing some basic unit testing on them seemed like a good exercise.
I’m also trying to use modern ES6+ features along with longer variable names to make the code more concise, hopefully without sacrificing too much readability. In order to experiment more with this concisenessreadability relationship, I opted for omitting comments altogether.
Please let me know where you think a comment would’ve made a big difference, and if you see any improvements that can be done to the variable names (along with any observation you have regarding the code in general).
The chosen ones are three from the O(n^2) family, and three from the O(n log n) family:
 Bubble Sort
 Selection Sort
 Insertion Sort
 Merge Sort
 Heap Sort
 Quick Sort
And for unit testing I’m using
 Mocha
 Chai
Since this project has dependencies and is larger than 100 lines of code, I’ve created a Github repository for our convenience here. Pull requests welcome!
Here is the code for the sorting algorithms
const bubbleSort = (nums) => {
let sorted = true
for (let loop = 0; loop < nums.length  1; loop++) {
for (let index = 0; index < nums.length  1  loop; index++) {
if (nums[index] > nums[index + 1]) {
[nums[index], nums[index + 1]] = [nums[index + 1], nums[index]]
sorted = false
}
}
if (sorted) break
}
return nums
}
const selectionSort = (nums) => {
for (let pivot = 0; pivot < nums.length  1; pivot++) {
let min = pivot
for (let swap = pivot + 1; swap < nums.length; swap++) {
if (nums[min] > nums[swap]) {
min = swap
}
}
[nums[pivot], nums[min]] = [nums[min], nums[pivot]]
}
return nums
}
const insertionSort = (nums) => {
for (let target = 0; target < nums.length; target++) {
let swap = target
while (swap > 0 && nums[swap  1] > nums[swap]) {
[nums[swap  1], nums[swap]] = [nums[swap], nums[swap  1]]
swap
}
}
return nums
}
const mergeSort = (nums) => {
const merge = (left, right) => {
const merged = []
while (left.length && right.length) {
merged.push(left[0] <= right[0] ? left.shift() : right.shift())
}
return [...merged, ...left, ...right]
}
const splitAndMerge = (array) => {
if (array.length < 2) return array
const mid = array.length / 2
const left = array.slice(0, mid)
const right = array.slice(mid, array.length)
return merge(splitAndMerge(left), splitAndMerge(right))
}
return splitAndMerge(nums)
}
const heapSort = (nums) => {
const heapifySubtree = (size, root) => {
const left = root * 2 + 1
const right = left + 1
let max = root
if (left < size && nums[left] > nums[max]) {
max = left
}
if (right < size && nums[right] > nums[max]) {
max = right
}
if (max !== root) {
[nums[max], nums[root]] = [nums[root], nums[max]]
heapifySubtree(size, max)
}
}
const heapifyArray = () => {
for (let index = Math.floor(nums.length / 2  1); index >= 0; index) {
heapifySubtree(nums.length, index)
}
}
const sort = () => {
heapifyArray()
for (let index = nums.length  1; index >= 0; index) {
[nums[0], nums[index]] = [nums[index], nums[0]]
heapifySubtree(index, 0)
}
}
sort()
return nums
}
const quickSort = (nums) => {
if (nums.length < 2) return nums
const pivot = nums[0]
const left = []
const right = []
for (let index = 1; index < nums.length; index++) {
nums[index] < pivot ? left.push(nums[index]) : right.push(nums[index])
}
return [...quickSort(left), pivot, ...quickSort(right)]
}
module.exports = {
bubbleSort,
selectionSort,
insertionSort,
mergeSort,
heapSort,
quickSort
}
And here is the code for the unit tests. I’m using Mocha with Chai, but as I understand it, the patterns used are very similar to Jasmine and Jest.
const { expect } = require('chai')
const sorting = require('./sortingalgorithms')
const testSubjects = [
sorting.bubbleSort,
sorting.selectionSort,
sorting.insertionSort,
sorting.mergeSort,
sorting.heapSort,
sorting.quickSort
]
const expectations = (sort) => () => {
expect(sort([])).to.deep.equal([])
expect(sort([7])).to.deep.equal([7])
expect(sort([1, 2, 3, 4])).to.deep.equal([1, 2, 3, 4])
expect(sort([2.3, 1, 0.5, 1.8])).to.deep.equal([1.8, 0.5, 1, 2.3])
}
const test = (sort) => () =>
it('sorts numeric array', expectations(sort))
const runTestOnSubject = (sort) =>
describe(`Sorting algorithm ${sort.name}`, test(sort))
testSubjects.forEach(runTestOnSubject)
Please share any comment / observation you might have regarding best practices, antipatterns, efficiency, or style. All code review contexts are very welcome! If you think anything can be improved, in any way, please let me know.
I do have some specific questions you might want to address:
I’ve used the ternary operator in two occasions. One in mergeSort, and one in quickSort.
merged.push(left[0] <= right[0] ? left.shift() : right.shift()) // mergeSort
nums[index] < pivot ? left.push(nums[index]) : right.push(nums[index]) // quickSort
Do you think this is hard to understand or follow? Should I’ve used if else
or another pattern to make these more readable? I went for the ternary because I feel like it helps make the code more expressive (say more with less) in these two instances, but if it makes them harder to read it probably isn’t worth it.
Did the code suffer too much from the lack of comments? Where do you think a comment would make a big difference?
Do you see variable names that can be improved?
Would you implement any of these algorithms differently, in order to improve the readability or efficiency?
Are the unit tests implemented correctly, and easy to read / follow? Would you have done something differently?
Solution

insertionSort
implementation is suboptimal.swap > 0 && nums[swap  1] > nums[swap]
does two compares at each iteration (and twice more data moves than necessary). It is possible to get away with only one comparison. Considerif (nums[0] > nums[swap]) { // nums[swap] shall land at the beginning of array. We don't care // about values. Just shift [0, swap) right by one. temp = nums[swap] while (swap > 0) { nums[swap] = nums[swap  1] swap } nums[0] = temp } else { temp = nums[swap] // nums[0] is a natural sentinel. Don't bother to test the indices. while (nums[swap  1] > temp) { nums[swap] = nums[swap  1] swap } nums[swap] = temp }

quickSort

The single most significant advantage of a quick sort is that it sorts inplace. The
left
andright
temporaries defeat it. It is not inplace anymore. 
There are at least two (not so obvious) optimizations.
First, one of the recursive calls is tailrecursive, and can be eliminated. I don’t know how good js is in detecting and eliminating tail recursion; anyhow it is a rare case when a programmer may outperform the compiler. Indeed the goal is to minimize the number of recursive calls; we want to recurse only into a smaller partition.
Second, when the partition become small, a cost of recursion overweights its benefits. Consider a cutoff limit
$O(nk)$k
, and don’t recurse into a smaller partition. Instead, insertionsort the array once the recursion phase finishes. Notice that by that time an array is almost sorted: every element is at mostk
places away from its final destination, so the cost of the insertionsort phase is O(nk). BTW this gives a hint that
$\mathrm{log}n$k
shall be in a ballpark of lognwithout hurting a performance.
