Sorting – Properties

Selection Sort:

  • Not stable
  • O(1) extra space
  • Θ(n2) comparisons
  • Θ(n) swaps
  • Not adaptive

 

Quick Sort:

  • Not stable
  • O(lg(n)) extra space
  • O(n2) time, but typically O(n·lg(n)) time
  • Not adaptive

 

Merge Sort:

  • Stable
  • Θ(n) extra space for arrays
  • Θ(lg(n)) extra space for linked lists
  • Θ(n·lg(n)) time
  • Not adaptive
  • Does not require random access to data

Insertion Sort:

  • Stable
  • O(1) extra space
  • O(n2) comparisons and swaps
  • Adaptive: O(n) time when nearly sorted
  • Very low overhead
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s