Skip to content

Merge vs Quick Sort

Quick Sort

  • internal algorithm
  • unstable | can be made
  • arrays preffered
  • small db
  • worst case -> O(n^2)
  • divide untill you can't (DAC) (any length)
  • partition exchange sort
  • pivot
  • in place
  • left of pivot < pivot < right of pivot
  • good cache locallity

Merge Sort

  • external
  • stable
  • link list preffered
  • any length db
  • worst case -> O(nlogn)
  • DAC (n/2)
  • 3 arrays -> 2 to sort, 1 to store | not in place