## 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.