Question :
Suppose a large array is maintained with the following policy. The array is initially sorted. When new elements are added, they are inserted at the end of the array and counted.
Whenever the number of new elements reaches 10, the array is resorted and the counter is clear. What strategy would be good to use for resorting the array in O(n)?
More specifically, assume that A[1..n] contains n elements sorted in increasing order. Then 10 new elements are added at the end of the array.
Design a sorting algorithm (using pseudocode) that resorts the array A[1 ellipsis n+10] in running time O(n).