Please explain Suppose a large array is maintained with the

Please explain...

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?

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…n+10] in running time O(n).

Solution

=====================================================
--------------
Answer:
--------------

  
   For resorting an Array of large number of elements. The best algorithm to choose is Insertion Sort. Since the existing elements
   are already in sorted fashion only the added extra elements to be taken care. It can achieved using insertion sort.
   Given array of A[1..n] contains n elements sorted in increasing order.
   After inserting 10 more elements to the array, The size of the array becomes A[1…n+10]

  
-------------------------------------------------------
Pseudocode for the Insertion sort :
-------------------------------------------------------

void insertionSort(int array[],int n)
{
int y;

//Since extra elements are 10, Sorting the remaining 10 digits
for(int k=n-10;k<n;k++)
{
       y=array[k];
      
       for(int i=k-1; i>=0 && y<array[i]; i--)
       {
           array[i+1]=array[i];
           array[i]=y;
       }
   }
}

----------------------------
Time Complexity:
----------------------------
   By taking large volume of array, first loop runs 10 X n times.
   In general the time complexity is O(n). Considering 10 to be least count.
  
=====================================================