Sorting

• Selection sort

  ---

  Selection sort is an in-place comparison sorting algorithm.

  Use cases

• Bubble sort

  ---

  Repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed.

  Use cases

• Insertion sort

  ---

  Builds the final sorted array (or list) one item at a time by comparisons.

  Use cases

• Merge sort

  ---

  Efficient, general-purpose, and comparison-based sorting algorithm.

  Use cases

• Quicksort

  ---

  Slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions.

  Use cases

• Heapsort

  ---

  Reorganizes an input array into a heap (a data structure where each node is greater than its children) and then repeatedly removes the largest node from that heap, placing it at the end of the array.

  Use cases

Performance overview

Sort	Time complexity	Space complexity
Selection sort	\(\color{white} \fcolorbox{crimson}{firebrick} {Ω(n^2)}\) → \(\color{white} \fcolorbox{crimson}{firebrick} {Θ(n^2)}\) → \(\color{white} \fcolorbox{crimson}{firebrick} {O(n^2)}\)	\(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Bubble sort	\(\color{black} \fcolorbox{gold}{yellow} {Ω(n)}\) → \(\color{white} \fcolorbox{crimson}{firebrick} {Θ(n^2)}\) → \(\color{white} \fcolorbox{crimson}{firebrick} {O(n^2)}\)	\(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Insertion sort	\(\color{black} \fcolorbox{gold}{yellow} {Ω(n)}\) → \(\color{white} \fcolorbox{crimson}{firebrick} {Θ(n^2)}\) → \(\color{white} \fcolorbox{crimson}{firebrick} {O(n^2)}\)	\(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)
Merge sort	\(\color{black} \fcolorbox{darkorange}{sandybrown} {Ω(n . log(n))}\) → \(\color{black} \fcolorbox{darkorange}{sandybrown} {Θ(n . log(n))}\) → \(\color{black} \fcolorbox{darkorange}{sandybrown} {O(n . log(n))}\)	\(\color{black} \fcolorbox{gold}{yellow} {O(n)}\)
Quicksort	\(\color{black} \fcolorbox{darkorange}{sandybrown} {Ω(n . log(n))}\) → \(\color{black} \fcolorbox{darkorange}{sandybrown} {Θ(n . log(n))}\) → \(\color{white} \fcolorbox{crimson}{firebrick} {O(n^2)}\)	\(\color{black} \fcolorbox{yellowgreen}{greenyellow} {O(log(n))}\)
Heapsort	\(\color{black} \fcolorbox{darkorange}{sandybrown} {Ω(n . log(n))}\) → \(\color{black} \fcolorbox{darkorange}{sandybrown} {Θ(n . log(n))}\) → \(\color{black} \fcolorbox{darkorange}{sandybrown} {O(n . log(n))}\)	\(\color{white} \fcolorbox{limegreen}{forestgreen} {O(1)}\)