User:Wesgarner/Comparisonofsortingalgorithms

Comparison of algorithms

Main Sorting Algorithms used in Java

Name	Average	Worst	Memory	Stable	Method	Other notes	Tiny code size
Selection sort	${\mathcal {O}}\left(n^{2}\right)$	${\mathcal {O}}\left(n^{2}\right)$	${\mathcal {O}}\left({1}\right)$	No	Selection	Its stability depends on the implementation.
Insertion sort	${\mathcal {O}}\left(n^{2}\right)$	${\mathcal {O}}\left(n^{2}\right)$	${\mathcal {O}}\left({1}\right)$	Yes	Insertion	Average case is also ${\mathcal {O}}\left({n+d}\right)$, where d is the number of inversions
Shell sort	—	${\mathcal {O}}\left({n\log ^{2}n}\right)$	${\mathcal {O}}\left({1}\right)$	No	Insertion
Binary tree sort	${\mathcal {O}}\left({n\log n}\right)$	${\mathcal {O}}\left({n\log n}\right)$	${\mathcal {O}}\left(n\right)$	Yes	Insertion	When using a self-balancing binary search tree
Insertion
Merge sort	${\mathcal {O}}\left({n\log n}\right)$	${\mathcal {O}}\left({n\log n}\right)$	${\mathcal {O}}\left(n\right)$	Yes	Merging
Quicksort	${\mathcal {O}}\left({n\log n}\right)$	${\mathcal {O}}\left(n^{2}\right)$	${\mathcal {O}}\left({\log n}\right)$	No