Sorting is how you turn a bunch of numbers into a sorted array. You can prove it takes at least time to sort arbitrary items in general, called the "comparison sort bound". HeapSort, MergeSort, and QuickSort all work on items in general, so they have this time limit. If you restrict yourself to sort integers or discretely spaced things, you can beat this bound. Counting Sort and Radix Sort are such algorithms, and that's why they're allowed to run faster, in and time. Time Space HeapSort /coding

Sorting

Sorting is how you turn a bunch of numbers into a sorted array.

You can prove it takes at least $O(n \log n)$ time to sort arbitrary items in general, called the "comparison sort bound". HeapSort, MergeSort, and QuickSort all work on items in general, so they have this time limit. 

If you restrict yourself to sort integers or discretely spaced things, you can beat this bound. Counting Sort and Radix Sort are such algorithms, and that's why they're allowed to run faster, in $O(n+|\text{range}|)$ and $O(n \cdot |\text{digits}|)$ time. 



\split{{

$$
\\[18bp]
$$
\tip3{Time}

\tip3{Space}



}}{{

\b{HeapSort}


$O(n \log n)$


$O(1)$

 \link{/coding/180,Link}

}}{{

\b{MergeSort}



$O(n \log n)$




$O(n)$

 \link{/coding/138,Link}

}}{{

\b{QuickSort}



$O(n \log n)$



$O(1)$

 \link{/coding/176,Link}

}}

\split{{
$$
\\[18bp]
$$

}}{{
\b{Non-Comparison ➡️}


}}{{



\b{Counting Sort}

$O(n +|\text{range}|)$



$O(n)$

\link{/coding/177,Link}
}}{{

\b{Radix Sort}



$O(n \cdot |\text{digits}|)$



$O(n)$

\link{/coding/404,Link}



}}







Python's built-in `.sort()` and `sorted()` functions run "TimSort" in the background, a variant of MergeSort. 




Strictly speaking, you don't need to master sorting algorithms for an interview. You might want to understand the basics of HeapSort and MergeSort to be safe. 


Iteration

Sorting