Aug 1999 AP207 : Advanced Programming Techniques (Question 5)

This question is concerned with the implementation of a sorting procedure that uses the insertion sort algorithm. The definition of a linked list type, a prototype for the procedure Insert, and the procedure InsertionSort are given below. Type List = ^Node; Node=RECORD Item : Integer; Next: List END; PROCEDURE Inset(x : List; VAR xs : List); PROCEDURE InsertionSort (VAR xs : List); VAR rest, singleton, result : List; BEGIN rest : =xs; result := Nil; WHILE (rest <> Nil) DO BEGIN singleton : = rest; rest : = rest^.Next; singleton^.Next : = Nil; Insert(singleton, result); END xs:= result END; The procedure insert (to be defined later) takes a singleton list x and a sorted xs as its arguments, and inserts the element stored in the singleton list into the sorted list such that the list xs remains sorted. For example, the figure below shows an example list before and after adding the singleton element 3 :
(a)	Informally describe the insertion sorting algorithm used in the Pascal procedure InsertSort above.	[3]
(b)	Given the list [5,3,4,1], draw four diagrams that show the states of the lists rest and result immediately after each execution of insert.	[8]
(c)	How many list elements would have to be traversed by all the invocations of the insert procedure given: (i) an already sorted list of size N passed to InsertionSort? i.e., what is the worst case cost, or upper-bound complexity of insertion sort? (ii) a list in decreasing order of values of size N passed to InsertionSort? i.e, what is the best case cost, or lower-bound complexity of insertion sort?	[1] [1]
(d)	Define the procedure Insert.	[7]