# JavaScript Algorithms: Quicksort

> Learn how the quicksort algorithm works in JavaScript, using recursion and a pivot to split an array into smaller and bigger items, with O(n log n) speed.

Author: [Flavio Copes](https://flaviocopes.com/about/) | Published: 2020-11-23 | Topics: [JavaScript](https://flaviocopes.com/tags/js/) | Canonical: https://flaviocopes.com/quicksort-javascript/

Quicksort is a more efficient searching algorithm than [selection sort](https://flaviocopes.com/selection-sort-javascript/), _in most cases_, and it makes use of recursion.

Recursion means we call a function from within the same function. It's a very useful practice, sometimes, and this is one of those cases.

I said "in most cases", because as we'll see, in the worst case bubble sort can take the same time of selection sort: `O(n^2)`. But in the best case scenario, it will run at `O(n log n)`, which is in the middle between `O(n)` and `O(n^2)`.

How does it work? Given an array, we pick an item, called _pivot_. We then get all the items smaller than the pivot, and the items bigger than the pivot.

Then we run the same operation on the 2 array that compose the smaller and bigger items.

It's easier to see the code than to describe it:

```js
const quickSort = (originalList) => {
  const list = [...originalList]

  if (list.length < 2) {
    return list
  }

  const pivot = list[0]

  const smaller = list.filter((item) => item < pivot)
  const bigger = list.filter((item) => item > pivot)

  return [...quickSort(smaller), pivot, ...quickSort(bigger)]
}
```

In this case I chose the pivot to be the first item in the array, but it could also be the item in the middle, for example:

```js
const pivot = list[Math(floor(list.length / 2)]
```

Notice how we first copy the array, so calling `quickSort()` does not modify the original array, it just returns a new sorted array:

```js
const a = [1, 6, 3, 4, 5, 1, 0, 4, 8]

console.log(quickSort(a))
//[0, 1, 1, 3, 4, 4, 5, 6, 8

console.log(a)
//[1, 6, 3, 4, 5, 1, 0, 4, 8]
```