Algorithm Worst Case Average Case Best Case Min. no. of swaps Max. no. of swaps
Bubble $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$
Selection $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$ 0 (when array is already sorted) $\theta(n^{2})$
Insertion $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n)$ (when array is sorted) 0 (when array is already sorted) $\theta(n^{2})$
Quick $\theta(n^{2})$ (when array is sorted, and pivot taken from one end) $\theta(n\lg n)$ $\theta(n\lg n)$ 0 (when array is already sorted) $\theta(n^{2})$
Merge $\theta(n\lg n)$ $\theta(n\lg n)$ $\theta(n\lg n)$ Is not in-place sorting Is not in-place sorting
Heap $\theta(n\lg n)$ $\theta(n\lg n)$ $\theta(n\lg n)$ $O(n\lg n)$ $\theta(n\lg n)$

In-Place Sorting

When sorting happens within the same array, its called in-place sorting. All the above sorting except, merge sort are in-place sorting. In merge sort, we use an auxiliary array for merging two sub-arrays

Stable sorting

This matters only for arrays with same element repeated. If $A[x] = A[y]$, in the original array such that $x<y$, then in the sorted array A[x] must be placed at position u and A[y] must be placed at position v, such that $u<v$.




blog comments powered by Disqus
Algorithm Worst Case Average Case Best Case Min. no. of swaps Max. no. of swaps
Bubble $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$
Selection $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n^{2})$ 0 (when array is already sorted) $\theta(n^{2})$
Insertion $\theta(n^{2})$ $\theta(n^{2})$ $\theta(n)$ (when array is sorted) 0 (when array is already sorted) $\theta(n^{2})$
Quick $\theta(n^{2})$ (when array is sorted, and pivot taken from one end) $\theta(n\lg n)$ $\theta(n\lg n)$ 0 (when array is already sorted) $\theta(n^{2})$
Merge $\theta(n\lg n)$ $\theta(n\lg n)$ $\theta(n\lg n)$ Is not in-place sorting Is not in-place sorting
Heap $\theta(n\lg n)$ $\theta(n\lg n)$ $\theta(n\lg n)$ $O(n\lg n)$ $\theta(n\lg n)$

In-Place Sorting[edit]

When sorting happens within the same array, its called in-place sorting. All the above sorting except, merge sort are in-place sorting. In merge sort, we use an auxiliary array for merging two sub-arrays

Stable sorting[edit]

This matters only for arrays with same element repeated. If $A[x] = A[y]$, in the original array such that $x<y$, then in the sorted array A[x] must be placed at position u and A[y] must be placed at position v, such that $u<v$.




blog comments powered by Disqus