Q1: Suppose you are given an array A of n Your task is to sort n numbers stored in array A by reading the first element of A and placing it on its original position (position after sorting). Then read...

Q1:
Suppose you are given an array A of
n
Your task is to sort
n
numbers stored in array A by reading the first element of A and placing it on its original position (position after sorting). Then read the second element of A, and place it on its original position. Continue in this manner for the first
n
-
1
elements of A. What type of sorting is this? Write the algorithm and also mention the name of this sorting algorithm. What loop invariant does this algorithm maintain? Give the best-case and worst-case running times of this sorting algorithm.