# Sorting

The fastest possible algorithm that uses comparisons to sort $$N$$ items must use $$\text{O}(N \log{N})$$ time.

## ![images](https://learning.oreilly.com/api/v2/epubs/urn:orm:book:9781119575993/files/images/c06-i0012.png) Algorithms <a href="#head-2-88" id="head-2-88"></a>

Sort algorithms such as insertion sort, selection sort & bubble sort are relatively simple but slow.

{% hint style="warning" %}
Their simplicity sometimes lets them outperform faster but more complicated algorithms for very small arrays.&#x20;
{% endhint %}

### ![images](https://learning.oreilly.com/api/v2/epubs/urn:orm:book:9781119575993/files/images/c06-i0063.png) Algorithms <a href="#head-2-89" id="head-2-89"></a>

Such as heap sort, quick sort, and merge sort, are more complicated but much faster.&#x20;

### Sub ![images](https://learning.oreilly.com/api/v2/epubs/urn:orm:book:9781119575993/files/images/c06-i0018.png) Algorithms <a href="#head-2-91" id="head-2-91"></a>

Sorting algorithms such as as counting sort and pigeonhole sort, don't use comparisons to sort items, so they can break the $$O(N \log{N})$$ barrier and perform amazingly fast under the right circumstances.





