Sorting (quicksort)

In this lecture, Prof Jonathan Shewchuk explains the Quicksort sorting algorithm, currently part of the Java library sort routine. Like various efficient sorting algorithms, including the mergesort used by the Java library, Quicksort is a recursive "divide and conquer" strategy.

Related pages on this site:

 Sorting Java collections
 Java sort algorithm
 Java sort performance

Lecture overview

TimeNotes / content / relevant pages on this site
0'00Introduction to Quicksort and overview of algorithm
15'00Choosing the pivot
23'00Quicksort on linked lists: extracting equal keys
28'40Comparison with mergesort
29'20Problem with extracting equal keys with array sort
30'25Choosing a random pivot with a linked list
31'00Quicksort on arrays: in-place sorting
41'00Dealing with keys the same as the pivot