Solution: Improving Quicksort

Solution

To avoid unwanted effects, it’s enough to split the input array into three subarrays: elements that are smaller, equal, and greater than the pivot. In the code below, we do this naively. We scan the array three times to collect the required elements.

Exercise break: Show how to partition the array into three parts (smaller, equal, and greater than the pivot) in place—that is, without allocating additional memory.

Code

Here is an implementation of the challenge. Click the “Run” button and observe the output.