Sorting Algorithms

https://www.bigocheatsheet.com/

Summary

• Selection Sort
  • Find the smallest and swap with the first
  • Runtime for best, average and worst-case: $O(n2)$
• Insertion Sort
  • Find where element $i$ goes and shift the rest to make room for element $i$
  • Runtime for best case is $O(n)$ and for average and worst case: $O(n^2)$
  • Works well for almost sorted array
• Merge Sort
  • Divide and Conquer - Split into halves, recurse, then merge
  • Runtime for best, average and worst-case: $O(n\log n)$
  • Does not use temp array
• Linear Search
  • Scan one by one until found

Lower Bounds for Sorting

What we have seen in CS240 - Data Structure and Data Management: