## How Quicksort works:

Similarly to merge sort, quicksort is a divide and conquer type of algorithm. Initially, a **pivot **is selected from the array. Then it partitions the elements into two sub arrays based on the condition if they are **less than **or **greater than** the **pivot**. Last, the sub arrays are sorted recursively.

## Quicksort complexity:

The complexity of the algorithm is **O(n^2) **though this case is rare and it only happens when the pivot that is picked is not good in a sense that we have to sort all the elements in each iteration. However, the average complexity is** O(nlogn)**.

## Implementation of Quicksort in JavaScript:

```
const quicksort = (array) => {
return quicksortRecusrive(array, 0, array.length - 1);
};
const quicksortRecusrive = (array, left, right) => {
if (left >= right) {
return;
}
const pivot = array[Math.trunc((left + right) / 2)];
const index = partition(array, left, right, pivot);
quicksortRecusrive(array, left, index - 1);
quicksortRecusrive(array, index, right);
return array;
};
const swap = (array, left, right) => {
const temp = array[left];
array[left] = array[right];
array[right] = temp;
};
const partition = (array, left, right, pivot) => {
while (left <= right) {
while (array[left] < pivot) {
left++;
}
while (array[right] > pivot) {
right--;
}
if (left <= right) {
swap(array, left, right);
left++;
right--;
}
}
return left;
};
console.log(quicksort([4, 3, 2, 5, 9, 67, 8, 5, 40, 6, 6]));
// [2, 3, 4, 5, 5, 6, 6, 8, 9, 40, 67]
```

The best explanation I found is from the author of "Cracking the coding interview" Gayle Laakmann McDowell.

If you want more information about the algorithm you can find more info here.