4.6.1 Example of Sorting

A list is first sorted and then after some use, a random element is included and then sorted. If we want to do this repeatedly, then amortized analysis will indicate insertion sort rather than heapsort or quicksort.