Recursive Insertion Sort | Recursive function to sort an array using insertion sort ; base case ; Sort first n - 1 elements ; Insert last element at its correct position in sorted array . ; Move elements of arr [ 0. . i - 1 ] , that are greater than key , to one position ahead of their current position ; A utility function to print an array of size n ; Driver program to test insertion sort
def insertionSortRecursive ( arr , n ) : NEW_LINE INDENT if n <= 1 : NEW_LINE INDENT return NEW_LINE DEDENT insertionSortRecursive ( arr , n - 1 ) NEW_LINE last = arr [ n - 1 ] NEW_LINE j = n - 2 NEW_LINE while ( j >= 0 and arr [ j ] > last ) : NEW_LINE INDENT arr [ j + 1 ] = arr [ j ] NEW_LINE j = j - 1 NEW_LINE DEDENT arr [ j + 1 ] = last NEW_LINE DEDENT def printArray ( arr , n ) : NEW_LINE INDENT for i in range ( n ) : NEW_LINE INDENT print arr [ i ] , NEW_LINE DEDENT DEDENT arr = [ 12 , 11 , 13 , 5 , 6 ] NEW_LINE n = len ( arr ) NEW_LINE insertionSortRecursive ( arr , n ) NEW_LINE printArray ( arr , n ) NEW_LINE