Modify the insertion sort algorithm of Special Topic 14.2 to sort a linked list.

Data from special topic 14.2

••

Special Topic 14.2 Insertion Sort Insertion sort is another simple sorting algorithm. In this algorithm, we assume that the initial sequence a[0] a[1]... a[k] of an array is already sorted. (When the algorithm starts, we set k to 0.) We enlarge the initial sequence by inserting the next array element, a[k + 1], at the proper location. When we reach the end of the array, the sorting process is complete. For example, suppose we start with the array 11 9 16 5 7 Of course, the initial sequence of length 1 is already sorted. We now add a[1], which has the value 9. The element needs to be inserted before the element 11. The result is 9 11 16 5 7 Next, we add a[2], which has the value 16. This element does not have to be moved. 9 11 16 5 7 We repeat the process, inserting a [3] or 5 at the very beginning of the initial sequence. 5 9 11 16 7