## Let’s sort by hand

Assume we have an array of random numbers and we need to sort it using QuickSort algorithm:

``[5, 2, 7, 9, 6, 1, 4, 5, 0]``

We need to create function `qsort` that will get an array as an argument and will return sorted array.

That’s how the call to the function will look like:

``qsort([5, 2, 7, 9, 6, 1, 4, 5, 0]);``

Let’s go inside the function and inspect how it will sort the array.

• At the first call we need to select `pivot` element from the array. There are multiple approaches how to select pivot, it can be chosen randomly, it can picked form the middle of an array or it can be just first element of an array. For simplicity we’ll just take first element and assign it to `pivot` variable and it will be equal to five in our case.
• Then we will create two empty arrays, named `left` and `right`. First one will have all elements with values that are less than pivot. And second will receive all other elements - greater or equal to pivot.
• Now we will go through the source array and place elements to the respective arrays by hand. Five is the pivot, we already took it from the source array, two goes to left, seven goes to right, nine goes to right, six goes to right, one goes to left, four goes to left, five goes to right and zero goes to left.
• Now we have pivot and two arrays that have elements that are less or greater than pivot. Result of our function call will be concatenation of sorted left array, pivot and sorted right array;
``````// call 1:
qsort([5, 2, 7, 9, 6, 1, 4, 5, 0]);
const pivot = 5;
const left = [2, 1, 4, 0];
const right = [7, 9, 6, 5];
return qsort([2, 1, 4, 0]).concat(5).concat(qsort([[7, 9, 6, 5]]));``````

On the next step we call `qsort` recursively for the left array that holds `[2, 1, 4, 0]`. We repeat all the actions we did before:

• Choose `pivot`, it will be equal to two
• Create empty `left` and `right` arrays and fill them with values comparing each element of source array to pivot: one goes to left, four goes to right, zero goes to left.
• Now result of this function call will be sorted left array, concatenated with pivot and sorted right array.
``````// call 2
qsort([2, 1, 4, 0]);
const pivot = 2;
const left = [1, 0];
const right = ;
return qsort([1, 0]).concat(2).concat(qsort); // [0, 1, 2, 4]``````

On the next step we will call `qsort` to sort array of two elements `[1, 0]`. We repeat all the steps:

• Choose `pivot`, it will be equal to one.
• Create `left` and `right` arrays and fill them with values. In our case `left` will hold just one element, zero. And `right` will be empty.
• And result of this call will be sorted left array, pivot and right array.
``````// call 3
qsort([1, 0]);
const pivot = 1;
const left = ;
const right = [];
return qsort().concat(1).concat(qsort([])); // [0, 1]``````

No we call `qsort` on array that just holds one element and obviously it doesn’t need to be sorted, we just return an array as it is.

``````// call 4
qsort();
return ;``````

We return in recursive calls one level up, concatenate `pivot` and make another recursive call to sort empty array. Similar to the previous call with one element, we don’t need to do anything with empty array, just return it back.

``````// call 5
qsort([]);
return [];``````

Now we go up to call three, return value that holds sorted array of two elements - `[0, 1]`, go up to call two, concatenate this value with pivot that is equals to two and concatenate to call for sorting of array from one element ``. We already know that this call will just return that array back:

``````// call 6
qsort();
return ;``````

And now from call two we return sorted array that holds four elements: `[0, 1, 2, 4]`. Now we go up to the very first call of our recursive function, we already have `left` array sorted, `pivot` concatenated and we need to sort `right` array. Everything will work exactly as we seen before. We get an array, choose pivot, create `left` and `right` arrays, fill them with values and return concatenation of sorted `left` array, `pivot` and sorted `right` array.

``````// call 7
qsort([7, 9, 6, 5]);
const pivot = 7;
const left = [6, 5];
const right = ;
return qsort([6, 5]).concat(7).qsort();``````

We won’t go deeper in recursive calls because they work the same way as we already seen before.

## Implementing recursive function in JavaScript

Now we will implement our function in JavaScript.

• We start function body by checking length of an array and if it is empty or has only one element, we return as it is.
• Next we use destructuring assignment and spread operator to get first element as `pivot` and place rest of the array to `rest` constant.
• Also we use `const` keyword to create two empty arrays `left` and `right`. Using `const` here may be confusing because we will change contents of the arrays, it simply means that identifiers `left` and `right` won’t be reassigned but it doesn’t tell that contents of arrays can’t be changed.
• Next we call `.forEach()` on `rest` array and compare each element with pivot, elements with lower values are put to the `left` and all others - to the `right`.
• At the last step we call `qsort` recursively on `left` array, concatenate `pivot` and result of `qsort` on right array.

That’s how our implementation will look like:

``````function qsort(arr) {
if (arr.length <= 1) {
return arr;
}
const [pivot, ...rest] = arr;
const left = [], right = [];
rest.forEach( el => el < pivot ? left.push(el) : right.push(el) );
return qsort(left).concat(pivot).concat(qsort(right));
}``````