As mentioned, we'll be doing some swapping
once the partitions are properly arranged. At a high level, using this strategy, we'll start with three groups:
- Index
0
tolow
- this is the "bottom group" - Index
low
tomid
- this is the "middle group" - Index
mid
tohigh
- this is the "top group"
The idea is to set these initial groups, and then have the top "grow downwards" -- meaning to swap and properly assign the elements in each group, from top to bottom. So we'll see a line like this get executed:
JAVASCRIPT
1swap(arr, mid, high--);
Same with the bottom, except reverse, the bottom will grow bottom-up:
JAVASCRIPT
1swap(arr, low++, mid++);