Sorting Algorithm Complexities

• Algorithm complexity in sorting measures operations, like comparisons, assignments, and swaps, needed to sort a list of $n$ items.
• The different complexities to consider are best-case, worst-case, and average complexity.

Notation

• Landau notation expresses algorithm complexity.
  • $O(f(n))$: Asymptotic upper bound
  • $\Omega(f(n))$: Asymptotic lower bound
  • $\Theta(f(n))$: Order of magnitude

Classical Sort Complexities

• Listed below are the complexities of various different sorting algorithms
  • Bubble Sort
    • Best: $O(n)$
    • Average: $O(n^2)$
    • Worst: $O(n^2)$
    • Space: $O(1)$
  • Selection Sort
    • Best: $O(n^2)$
    • Average: $O(n^2)$
    • Worst: $O(n^2)$
    • Space: $O(1)$
  • Insertion Sort
    • Best: $O(n)$
    • Average: $O(n^2)$
    • Worst: $O(n^2)$
    • Space: $O(1)$
  • Quick Sort
    • Best: $O(n \log(n))$
    • Average: $O(n \log(n))$
    • Worst: $O(n^2)$
    • Space: $O(\log(n))$
  • Merge Sort
    • Best: $O(n \log(n))$
    • Average: $O(n \log(n))$
    • Worst: $O(n \log(n))$
    • Space: $O(n)$
  • Heap Sort
    • Best: $O(n \log(n))$
    • Average: $O(n \log(n))$
    • Worst: $O(n \log(n))$
    • Space: $O(1)$
  • Counting Sort
    • Best: $O(n + k)$
    • Average: $O(n + k)$
    • Worst: $O(n + k)$
    • Space: $O(k)$
  • Radix Sort
    • Best: $O(nk)$
    • Average: $O(nk)$
    • Worst: $O(nk)$
    • Space: $O(n + k)$
• $k$ is the value range of elements to be sorted.

Quadratic Sorts

• These sorts generally have a complexity of $O(n^2)$

Bubble Sort

• Adjacent elements are compared and swapped if out of order, repeating until no swaps occur.

Selection Sort

• The smallest list element is found and swapped with the first element; this is repeated for the rest of the list.

Insertion Sort

• A sorted part is maintained at the beginning; each element is inserted into its correct position in the sorted part.

"Divide to Conquer" Sorts

• Divide and conquer sorts use a divide and conquer method to improve runtime

Quick Sort

• A pivot is chosen, and the list partitioned into sub-lists of elements less than and greater than the pivot; the sub-lists are recursively sorted.

Merge Sort

• The list is divided into two equal sub-lists, which are recursively sorted and then merged into a single sorted list.

Heap Sort

• A binary heap is built from the list. The largest heap element (root) is extracted and placed at the end of the list. The process repeats with the remaining heap.

Non-Comparative Sorts

• Non-comparative sorts do not rely on comparing elements to sort

Counting Sort

• The number of occurrences of each list element are counted. These counts determine each element's position in the sorted list.

Radix Sort

• Elements are sorted by digits, least significant first. A stable sort (e.g., counting sort) is used for each digit.