CS314 - sorts and cases

Each sort and their big O.

Quicksort, best case?

O(nlogn)

Quicksort, average case?

O(nlogn)

Quicksort, worst case?

O(n²)

Quicksort, stability?

Unstable

Quicksort, type of sort?

In-place

Selection sort, best case?

O(n²)

Selection sort, average case?

O(n²)

Selection sort, worst case?

O(n²)

Selection sort, stability?

Unstable

Selection sort, type of sort?

In-place

Insertion sort, best case?

O(n)

Insertion sort, average case?

O(n²)

Insertion sort, worst case?

O(n²)

Insertion sort, stability?

Stable

Insertion sort, type of sort?

In-place

Mergesort, best case?

O(nlogn)

Mergesort, average case?

O(nlogn)

Mergesort, worst case?

O(nlogn)

Mergesort, stability?

Stable

Radix sort, best case?

O(nlogn)

Radix sort, average case?

O(nlogmaxval)

Radix sort, worst case?

O(nlogn)

Radix sort, stability?

Stable

Radix sort, type of sort?

Out of place