# Quick sort

## Definition

Quicksort is a divide and conquer sorting algorithm. It first divides a large array into two smaller subarrays and then recursively sorts the subarrays.

## Implementation

• Use recursion.
• Use the spread operator (...) to clone the original array, arr.
• If the length of the array is less than 2, return the cloned array.
• Use Math.floor() to calculate the index of the pivot element.
• Use Array.prototype.reduce() and Array.prototype.push() to split the array into two subarrays. The first one contains elements smaller than or equal to pivot and the second on elements greater than it. Destructure the result into two arrays.
• Recursively call quickSort() on the created subarrays.
const quickSort = arr => {
const a = [...arr];
if (a.length < 2) return a;
const pivotIndex = Math.floor(arr.length / 2);
const pivot = a[pivotIndex];
const [lo, hi] = a.reduce(
(acc, val, i) => {
if (val < pivot || (val === pivot && i != pivotIndex)) {
acc[0].push(val);
} else if (val > pivot) {
acc[1].push(val);
}
return acc;
},
[[], []]
);
return [...quickSort(lo), pivot, ...quickSort(hi)];
};

quickSort([1, 6, 1, 5, 3, 2, 1, 4]); // [1, 1, 1, 2, 3, 4, 5, 6]

## Complexity

The algorithm has an average time complexity of O(n log n), where n is the size of the input array.

## More like this

• Collection · 108 snippets

### JavaScript Arrays

Master array manipulation in JavaScript with this ES6 snippet collection.

• JavaScript ·

### Heap sort

Sort an array of numbers, using the heapsort algorithm.

• JavaScript ·

### Merge sort

Sort an array of numbers, using the merge sort algorithm.

• JavaScript ·

### Bucket sort

Sort an array of numbers, using the bucket sort algorithm.

Start typing a keyphrase to see matching snippets.