CS 240 Sorting Algorithms

Insertion sort worst case

O(n²)

Insertion sort best case

O(n)

Insertion sort average case

O(n²) because it takes n(n+1)/4 (eg sumation i/2) for the first loop

Is insertion sort stable?

Yes

Bubble sort best case

O(n²)

Bubble sort worst case

O(n²)

Bubble sort average case

O(n²)

Is Bubble sort stable?

Yes

Merge sort best case

O(nlogn)

Merge sort average sort

O(nlogn)

Merge sort worst case

O(nlogn)

Is merge sort stable?

Yes

Quick sort best case

O(nlogn)

Quick sort average case

O(nlogn)

Quick sort worst case

O(n²)

Radix sort worst case

O(n*d)

Radix sort average case

O(n*d)

Radix sort best case

O(n*d)

Selection Sort worst case

O(n²)

Selection Sort average case

O(n²)

Selection Sort best case

O(n²)

Selection Sort stable

No it is not stable