Recursive version of Insertion Sort
  • basicsorting
  • sorting
  • recursion
  • insertionsort
  • timecomplexity
  • array
  •   
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (25765)

Insertion sort can be expressed as a recurrence procedure. In order to sort A[1,2,....n] , we recursively sort A[1,2,....(n-1)] and then insert A[n] into the sorted array A[1,2,....(n-1)] . How will you write the running time of this recursive version of insertion sort.


Posted Answers

\(
T(n)=\left\{\begin{array}{ll}
O(1) & \mbox{if $n$ = 1}\\
T(n-1) + O(n) & \mbox{if $n >$ 1}
\end{array}\right. \
\)

\( T(n - 1) \) - For recursively sorting the previous (n - 1) elements.
\( O(n) \) - Running time for choosing the appropriate position of the element in the sorted array.

\(
T(n) = T(n-1) + n \\
\hspace{0.75cm} = n + (n-1) + T(n-2) \\
\hspace{0.75cm} = n + (n-1)+ (n-2)+ T(n-3) \\
\hspace{0.75cm} = n + (n-1)+ (n-2)+ ....+2 + T(1) \\
\hspace{0.75cm} = n(n-1)/2 + \theta (1) \\
\hspace{0.75cm} = \theta (n^{2}).
\)

So, \( T(n) = O(n^{2}). \)

public static int[] RecursiveInsertionSort(int[] array, int n) {
int i;
if (n > 1)
RecursiveInsertionSort(array, n - 1);
else {
int k = array[n];
i = n - 1;
while (i >= 0 & & array[i] > k) {
array[i + 1] = array[i];
i = i - 1;
}
array[i + 1] = k;
}
return array;
}

You need to Sign In to post your solution.