Sort Algorithms - rFronteddu/general_wiki GitHub Wiki

Algorithm Best Case Average Case Worst Case Note Description
Bubble Sort O(n) $O(n^2)$ $O(n^2)$ Best: already sorted. Compare neighbors, swap them if not in order
Worst: reverse sorted.
Selection Sort $O(n^2)$ $O(n^2)$ $O(n^2)$ fixed nature. Repeatedly select min/max element from unsorted portion and swap with first unsorted element
Insertion sort O(n) $O(n^2)$ $O(n^2)$ Best: already sorted. Compare values in turn, shift to left until a smaller value is found
Worst: reverse sorted.
Merge Sort O(n log n) O(n log n) O(n log n) Always O(n log n) due to merging. Divide, sort recursively, merge sorted sublists.
Quick Sort O(n log n) O(n log n) $O(n^2)$ Best: Pivot divides array evenly. Recursively partition based on pivot, moving smaller numbers to the left of the partition
Average: Random pivot selection.
Worst: Poor pivot selection.
Heap Sort O(n log n) O(n log n) O(n log n) Always O(n log n) due to heap property. Remove first element from max heap, place it at the end and reduce size. Heapify and repeat.
  • Insertion sort
    • Use in very small data sets, especially when nearly sorted,
  • Bubble Sort
    • Use for simplicity and nearly sorted data (best is O(n)); avoid for large datasets.
  • Selection Sort
    • for small datasets or when memory writes are costly
  • Heap Sort
    • Use for in-place sorting and worst-case guarantees O (n log n); avoid for stability (preservation of original relative order between equal elements) and average performance concerns.
  • Merge Sort
    • Use for stable sorting, linked lists (does not require random access), and external sorting; avoid when memory is limited (requires extra O(n) space).
  • Quick Sort
    • Use for average-case O(n log n) performance, in-place sorting, and randomized data; avoid for worst-case performance and stability.