Sorting and searching lists

Sorting algorithms

Sorted lists

There can be a total ordering on elements in a list.

We want to return a list such that only the ordering is changed.

\(\forall nm [list[n]>list[m] \leftrightarrow n>m]\)

Checking a sortable list

Sorting algorithms

Efficient in time and memory

Popular algorithms are:

  • Merge sort

  • Quick sort

  • Heap sort

Sorting linked lists

Search algorithms

Getting the max and min

Identifying the location of an element in a list