srsandy/ArraySortingAlgorithmsComplexity.md

## ArraySortingAlgorithmsComplexity.md

      
    Raw
  

              ArraySortingAlgorithmsComplexity.md
            
          
    Array Sorting Algorithms Complexity


Name
Best
Average
Worst
Memory
Stable
Comments


Bubble sort
n
n²
n²
1
Yes


Insertion sort
n
n²
n²
1
Yes


Selection sort
n²
n²
n²
1
No


Heap sort
n log(n)
n log(n)
n log(n)
1
No


Merge sort
n log(n)
n log(n)
n log(n)
n
Yes


Quick sort
n log(n)
n log(n)
n²
log(n)
No
Quicksort is usually done in-place with O(log(n)) stack space


Shell sort
n log(n)
depends on gap sequence
n (log(n))²
1
No


Counting sort
n + r
n + r
n + r
n + r
Yes
r - biggest number in array


Radix sort
n * k
n * k
n * k
n + k
Yes
k - length of longest key
Name	Best	Average	Worst	Memory	Stable	Comments
Bubble sort	n	n²	n²	1	Yes
Insertion sort	n	n²	n²	1	Yes
Selection sort	n²	n²	n²	1	No
Heap sort	n log(n)	n log(n)	n log(n)	1	No
Merge sort	n log(n)	n log(n)	n log(n)	n	Yes
Quick sort	n log(n)	n log(n)	n²	log(n)	No	Quicksort is usually done in-place with O(log(n)) stack space
Shell sort	n log(n)	depends on gap sequence	n (log(n))²	1	No
Counting sort	n + r	n + r	n + r	n + r	Yes	r - biggest number in array
Radix sort	n * k	n * k	n * k	n + k	Yes	k - length of longest key