Saturday, July 23, 2022

Data structures and algorithms cheat sheet - Sorting algorithms comparison

Data structures and algorithms cheat sheet, sorting algorithms quick reference, comparison of sorting algorithms on auxiliary space used, sorting algorithms cheat sheet, stable vs in-place vs comparison sorting algorithms quick reference

 

Sorting algorithms - A comparison

Algorithm

Time complexity

Space complexity

In-place

Stable

Comparison

No. of comparisons

Best

Average

Worst

Total

Auxiliary

Min

Max

Bubble sort

O(n)

O(n2)

O(n2)

O(n)

O(1)

Yes

Yes

Yes

n(n-1)/2

n(n-1)/2

Selection sort

O(n2)

O(n2)

O(n2)

O(n)

O(1)

Yes

No

Yes

n(n-1)/2

n(n-1)/2

Insertion sort

O(n)

O(n2)

O(n2)

O(n)

O(1)

Yes

Yes

Yes

n-1

n(n-1)/2

Merge sort

O(n log n)

O(n log n)

O(n log n)

O(n)

O(n)

No

Yes

Yes

n*log 2 n

n*log 2 n

Quick sort

O(n log n)

O(n log n)

O(n2)

O(n)

O(1)

Yes

No

Yes

n*log2n 

n(n-1)/2

Heap sort

O(n log n)

O(n log n)

O(n log n)

O(n)

O(1)

Yes

No

Yes

n*log2n

n*log2n

Bucket sort

O(n+k)

O(n+k)

O(n2)

O(n+k)

 

No

Yes

No

Depends on the algorithm used to sort the elements in each bucket

Radix sort

O(nk)

O(nk)

O(nk)

O(n+k)

 

Yes

Yes

No

NA

Shell sort

O(n log n)

O(n log2n)

O(n log2n)

O(n)

O(1)

Yes

No

Yes

n*log2n

 

 

Notations used

  • n refers to number of elements to be sorted.
  • k in Bucket sort refers to number of buckets, in Radix sort refers to the maximum length of the input elements. 

 

Auxiliary Space

is the temporary space allocated by your algorithm to solve the problem, with respect to input size.

 

Space Complexity

is the total space used by your algorithm to solve the problem, with respect to input size. Note that the Space Complexity includes input size.

 

In-place sorting algorithm

A sorting algorithm is in-place if it requires only O(1) extra space to sort the array.

 

Stable sorting algorithm

We say that a sorting algorithm is stable if, when two records have the same key, they stay in their original order. A sort is stable if two elements with the same value maintain their same relative order before and after the sort is performed.

 

Comparison sorting algorithm

Any sort algorithm using comparisons between keys (elements), and nothing else about the keys, to arrange items in a predetermined order (ascending or descending). The predetermined sorted order is determined by a sequence of comparisons between pairs of elements.


********************

Related links

Go to Data structures home page

 

Sorting algorithm comparison on time and space complexity

Sorting algorithm comparison on stability, and auxiliary space usage

Data structures and algorithms cheat sheet

Sorting algorithms quick reference 

Comparison of sorting algorithms in DSA on space utilized

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery