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];
};

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.