Sort

Basic ideas:

• Selection sort: Find the smallest item, put it at the front.

• Heap sort: Use MaxPQ to find the maximum element, put it at the front.

• Merge sort: Merge two sorted halves into one sorted whole.

• Insertion sort: Determine where to insert the current item.

• Quick sort: Partition the array into two halves around a pivot, then recursively sort the subarrays.

Method	Best Case Runtime	Worst Case Runtime	Space	Notes
Selection Sort	$\Theta (N²)$	$\Theta(N²)$	$\Theta(1)$
Heap Sort	$\Theta (N)^*$	$\Theta(N \log N)$	$\Theta(1)$	Bad cache performance.
Merge Sort	$\Theta(N \log N)$	$\Theta(N \log N)$	$\Theta(N)$
Insertion Sort	$\Theta(N)$	$\Theta(N²)$	$\Theta(1)$	Best for small N or almost sorted.