Data structures

Procedure Insertion Sort defined below sorts items of an array A[1..n] according to keys. The key at A[0] is assumed to be smaller then all keys of the range A[1..n). Assume that the operation swap takes constant time. In addition to estimating running times identify best and worst cases in terms of the input data. Hint: Observe that the number of executed swap operations substantially depends on the input data not only on the size n. A[0].key := the smallest key; for i:= 2 to n do begin j:= i; while A[j].key