Course section

Sorting Algorithms

Rearrange data using elementary, divide-and-conquer, distribution, and external sorting techniques.

10 topics

Sorting Foundations

Sorting algorithms are compared by time, extra space, stability, adaptiveness, and whether they operate in-place.

Bubble sort repeatedly swaps adjacent inversions, moving the largest remaining value to the end of each pass.

Selection sort repeatedly selects the minimum remaining value and places it at the next output position.

Insertion sort grows a sorted prefix by shifting larger values and inserting each new element into its correct position.

Shell sort performs insertion sorts over decreasing gaps so distant inversions are removed before the final gap-one pass.

Merge sort recursively divides the input, sorts both halves, and linearly merges the sorted results.

Quick sort partitions values around a pivot and recursively sorts the two resulting regions.

Counting sort counts occurrences of integer keys in a bounded range, avoiding comparison sorting entirely.

Radix sort processes keys one digit at a time using a stable sub-sort such as counting sort.

External sorting handles data larger than RAM by sorting memory-sized runs and merging them with sequential disk access.