Iteration

Sorting

Lesson

Two Classes of Sorting:

1. You can prove it takes at least O(nlog⁡n)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.

2. 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+∣range∣)O(n+|\text{range}|) and O(n⋅∣digits∣)O(n \cdot |\text{digits}|) time.

Good to know:

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

Chart:

-

Time

Space

HeapSort

O(nlog⁡n)O(n \log n)

O(1)O(1)

MergeSort

O(nlog⁡n)O(n \log n)

O(n)O(n)

QuickSort

O(nlog⁡n)O(n \log n)

O(1)O(1)

Counting Sort

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

O(n)O(n)

Radix Sort

O(n⋅∣digits∣)O(n \cdot |\text{digits}|)

O(n)O(n)

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.

Mark as Completed:
Submits:
test
Test your code to get an output here!