Learning materials

Chapter 3: Sorting (Elemental, Merge, Quick)

On this page

Visualizations

Visualizations may help make the sorting steps easier to follow. Start with our Card Sort Visualizer, which demonstrates selection, insertion, merge, and textbook quick sort. The resources below cover additional algorithms and implementations.
- visualgo.net
- Data Structure Visualization
Categories
- Comparison based
  - Best algorithm complexity $\Theta(n \log n)$
  - The base type must be comparable (can use >, <, ==, etc.)
  - selection
  - insertion
  - bubble
  - shell
  - quick
  - merge
  - heap - to be covered in the next chapter
- Other (special requirements on the data type)
  - Bucket
  - Radix
  - Counting
Complexity
- simple $\Theta(n^2)$: insert, selection, bubble
- fast $\Theta(n \log n)$: quick, merge, heap
- linear
  - radix $\Theta(nk) = \Theta(n)$
  - bucket $\Theta(n + k) = \Theta(n)$
Storage Space
- in-place
  - iterative sorting algorithms $\Theta(1)$
  - recursive sorting algorithms $\Theta(\log n)$ to $\Theta(n)$ (due to the recursion stack)
- not-in-place (out-of-place)
  - Merge sort $\Theta(n)$

Comparison based sorting algorithms

In-place swap based sorting algorithms
- Selection sort
- Insertion sort
- Bubble sort
- Shell sort
Divide and conquer sorting algorithms
- Merge sort
- Quick sort
Hybrid sorting algorithms
- Divide and conquer to reduce the problem size
- in-place swap based sorting algorithms to sort when the problem size is small