申論題

3. Two-way insertion sort : Suppose the output sorted sequence is increasing. The two-way insertion sort is a modification of the simple insertion sort (straightforward insertion sort), described as follows. After read the input elements, a separate output array a[0], a[1], a[2], a[n-1] is used to store the sorted sequence. This output array acts as a circular structure, that is, the right position of a[i] is a[i+1] if 0≤ i ≤ n-2, and the right position of a[n-1] is a[0]. The first input element is put into a[0] initially. Once a contiguous group of elements are in the array, room for a new input element is made by shifting all smaller  elements one step to the left or all larger element one step to the right. The choice of left-shift or right-shift to perform depends on which would cause the smallest amount of shifts. Use the following 6 input elements to illustrate how this algorithm works. You have to show the content of the output array after each input element is inserted into the array.