The Sorting Problem

The sorting problem involves taking a list of things that can be compared to each other to decide their order and then sorting them into ascending order (actually non-decreasing, since you can have multiple items with the same value, but, this was supposed to be the plain-English version).

• Preconditions: The input is a list of n orderable items, possibly with repetitions.
• Postconditions: The output is a list of the same n items in non-decreasing order.

• The Bubble Sort
• Selection Sort
• Insertion Sort
• The Mergesort
• Quicksort
• Heap!

• How To Think About Algorithms
• Introduction to the Design & Analysis of Algorithms (Levitin)