Quicksort in JavaScript using destructuring and spread syntax

Question

I'm learning Haskell, and there was quicksort implementation, so I thought that I could implement it in a similar way in JavaScript. The result:

const quicksort = ([x, ...xs], compareFn = (a, b) => a - b) => {
 // If x is undefined, the array is empty
 if (x === undefined) return [];
 const smallerSorted = quicksort(xs.filter(a => compareFn(a, x) <= 0), compareFn);
 const biggerSorted = quicksort(xs.filter(a => compareFn(a, x) > 0), compareFn);
 return [...smallerSorted, x, ...biggerSorted];
};
// Example usage:
console.log(quicksort(
 Array.from({ length: 10 }).map(_ => Math.floor(Math.random() * 100))
));
console.log(quicksort(
 Array.from('a quick brown fox jumped over a lazy dog'),
 (a, b) => a.charCodeAt(0) - b.charCodeAt(0)
).join(''));

.as-console-wrapper { max-height: 100% !important; }

I realize that calling filter() twice might be inefficient, so I made an alternative version, using the _.partition() function from Lodash:

const quicksort = ([x, ...xs], compareFn = (a, b) => a - b) => {
 // If x is undefined, the array is empty
 if (x === undefined) return [];
 const [smallerSorted, biggerSorted] = _.partition(
 xs,
 a => compareFn(a, x) <= 0
 ).map(arr => quicksort(arr, compareFn));
 return [...smallerSorted, x, ...biggerSorted];
};

• C Smith: Why exactly are you wanting this to be reviewed? You mention efficiency, so is the most efficient algorithm your goal?
• Zorgatone: javascript's functional-style looping methods are slow. es. myarr.forEach, myarr.map etc.. use regular while\do-while or for loops instead

Answer 1

Interesting question;

your quicksort is far slower than the regular sort, and is harder to read. You can find details here: https://jsperf.com/codereview-js-quicksort/15

But in essence this implementation is 90% slower than a regular sort. Using CPU profiling I can tell that most of the time is spent in _.partition which makes sense. Plus you keep creating functions like arr => quicksort(arr, compareFn) in every call of quicksort which adds up. Finally, that name should really be quickSort; JavaScript functions follow the lowerCamelCase convention.

My counter proposal would simply be:

console.log(
 Array.from('the quick brown fox jumps over the lazy dog').sort(
 (a, b) => a.charCodeAt(0) - b.charCodeAt(0)
 ).join('')
);

Historically, I have never heard of folks beating the native sort.