Linear-Time Median Algorithm (Making Quicksort go Fast!)

Here we show that we can find the median of an array (or in general, the kth smallest element) in linear time, versus just sorting the array and returning the kth element. This in turn speeds up Quicksort, because the pivot can now be the median element (findable in linear time), and we now get the guaranteed performance of Mergesort, which was O(n log n). Before, Quicksort can at worst pick the "first" element every time, which caused a O(n^2) runtime to occur.

Timestamps:
0:00 - Intro
0:31 - Problem Statement
3:28 - Can we find a good pivot?
6:37 - Generalize the problem (finding kth smallest/largest)
7:45 - Kth Smallest/Largest "Simple" Recursive Algorithm
13:25 - Can we make this algorithm faster?
15:10 - Median of Medians
20:50 - Modifying Kth Smallest/Largest Algorithm
24:55 - Proving this algorithm is faster
29:00 - Determining algorithm runtime

Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon:   / easytheory  
Discord:   / discord  

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierar...
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-f...

If you like this content, please consider subscribing to my channel:    / @easytheory  

Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀
[email protected]

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.