Sorting Algorithms Summary

• O(N²) in average and worst case; no extra memory required; stable.
  
• Bubble sort
• Uses about N²/2 comparisons and N²/2 exchanges on the average and in the worst case.
  
• Selection sort
• Find the smallest element in the array and exchange it with the element in the first position. Then repeat for 2nd, 3rd,...,nth positions.
  
• Uses about N²/2 comparisons and N exchanges.
  
• Each item is moved at most once.
• Method of choice for sorting files with very large records.
  
• Insertion sort
  
• Consider the elements one at a time, inserting each in its proper place among those already considered, keeping them sorted.
  
• Is linear for "almost sorted" files.
  
• Uses about N²/4 comparisons and N²/8 exchanges on the average; twice as many in the worst case.
• Uses sentinel value to avoid having extra boundary check in inner loop.