# Algorithm Analysis of Insertion Sort

Why is the recurrence formula for insertion sort is T(n-1) + n?

I understand the T(n-1) part but the why does the cost for merging results is n or linear. Do we have to merge in insertion sort?

Input: array $$A_1,\ldots,A_n$$
1. If $$n = 1$$, output $$A_1$$. Otherwise, continue.
2. Recursively sort $$A_1,\ldots,A_{n-1}$$ into $$B_1,\ldots,B_{n-1}$$.
3. Insert $$A_n$$ into $$B$$.
4. Output $$B$$.
If we denote by $$T(n)$$ the running time for arrays of length $$n$$, then step 2 takes time $$T(n-1)$$, whereas step 3 takes time $$O(n)$$. Combined, we get the recurrence $$T(n) = T(n-1) + O(n)$$, with base case $$T(1) = O(1)$$, corresponding to step 1.