Although Python has efficient sort functions built-in, writing sort algorithms is a good way to develop programming skills. In the last lab you will write two simple types of sorts: a "bubble" sort and a "merge" sort.
Bubble Sort
A bubble sort works by "bubbling" the smallest value to the top of the list. This ensures the first value is the smallest one. Then we use the same algorithm on the rest of the list. When the list to be sorted is only one element long we are done.
You can use two nested loops or a recursive approach.
Complexity
Although a bubble sort is relatively simple, it requires $n+(n-1)+...1=\frac{n(n+1)}{2}=\frac{n^2}{2}+\frac{n}{2}$ operations where $n$ is the number of elements to be sorted. The highest-order term is proportional to $n^2$ so we say the complexity of the algorithm is "Order of $n^2$" or $O(n^2)$.
Merge Sort
A "merge" sort is more efficient. We divide the list into two approximately-equal halves. Then we sort each half and merge the sorted sub-lists. The merge operation is relatively fast since we only need to compare the elements at the top of the two lists.
How do we sort each half? Easy -- we recursively call our merge-sort function until each list has only one (or zero) element(s) in it which is trivial to sort (a list with zero or one elements is already sorted).
Complexity:
Since we reduce the size of the list by half in each merge step, the number of merge operations is $\log_2n$. Each merge operation requires $n$ operations (selecting and copying the $n$ values from the sub-lists). The overall algorithm thus requires $O(n\log_2n)$ operations which is $\frac{n}{\log_2n}$ times faster.
For example, for a million elements ($n\approx2^{20}$) the merge sort would be about 50,000 times faster.
There are many other sort algorithms. Some have different behaviour such as not reordering values unless they are out of order. Others are optimized for specific applications such as sorting on disk (slow, sequential access) instead of in memory (fast, random access).