Sorting Characteristics

Algorithm	Comparison	In-place	Stable	Worst-case	Average-case
Insertion sort	Yes	Yes	Yes	$\Theta(n^2)$	$\Theta(n^2)$
Merge sort	Yes	No	Yes	$\Theta(nlgn)$	$\Theta(nlgn)$
Heap sort	Yes	Yes	No	$O(nlgn)$	-
Quick sort	Yes	Yes	No	$\Theta(n^2)$	$\Theta(nlgn)\ (expected)$
Counting sort	No	No	Yes	$\Theta(n+k)$	$\Theta(n+k)$
Radix sort	No	No	Yes	$\Theta(d(n+k))$	$\Theta(d(n+k))$
Bucket sort	No	No	Yes	$\Theta(n^2)$	$\Theta(n)\ (average\ case)$

Comparison Sort

• Input array의 elements간 compare operation을 수행하는지.

In-place Sort

• Input data structure에 대한 constant storage만을 사용하는지.

Stable Sort

• Input data structure의 sorted key를 유지하는 방식인지.