sorting = arranging a collection of items in order

e.g. arrays, linked lists, files

typically, sorting is done in ascending or descending order

typically, items are sorted based on an ordering relation of that property

e.g. numerically, alphabetically

the sorting problem

we want a function sort(ordered collection, lo, hi); that sorts an ordered collection of items from index lo to index hi

e.g. to sort an array a[N], we would call sort(a, 0, N-1)

preconditions:

lo, hi are valid indexses of the collection (i.e., 0 ≤ lo < hi ≤ N-1)

a[lo..hi] contains defined values of type Item

postconditions:

a[lo..hi] contains the same set of values as before the sort

for each i in lo..hi-1, we have that a[i]a[i + 1]

in-place sort = sorting algorithms that directly modifies the original collection to sort (no copies of the array made etc. that cost extra memory)

stable sort = a sorting algorithm that maintains the order of duplicate values

given that x == y, if x preceeds y in an unsorted list, x also preceeds y in a sorted list

adaptive sort = performance is affected by the actual values of items

i.e., best, average and worse cast performance differs

e.g. bubble sort has $\Omega$(n) and O(n^2)

sorting complexity

we focus on three main cases: how quickly does our algorithm sort a collection in…