Mastering JavaScript Functional Programming - Second Edition

Divide and conquer – sorting

We can see another example of the divide and conquer strategy with sorting. A way to sort arrays, called quicksort, is based upon the following steps:

1. If your array has 0 or 1 elements, do nothing; it's already sorted (this is the base case).
2. Pick an element of the array (called the pivot) and split the rest of the array into two subarrays: the elements smaller than your chosen element and the elements greater than or equal to your chosen element.
3. Recursively sort each subarray.
4. Concatenate both sorted results, with the pivot in-between, to produce the sorted version of the original array.

Let's see a simple version of this (there are some better-optimized implementations, but we are interested in the recursive ...