Insertion Sort Recursive Function (possible to do with 2 recursive functions?)

[sindhu05]

Please see the following recursive code of Insertion sort (this is easily available online and I have also taken one from one such site)

void insertionSortRecursive(int arr[], int n) 
{ 
    // Base case 
    if (n <= 1) 
        return; 
  
    // Sort first n-1 elements 
    insertionSortRecursive( arr, n-1 ); 
  
    // Insert last element at its correct position 
    // in sorted array. 
    int last = arr[n-1]; 
    int j = n-2; 
  
    /* Move elements of arr[0..i-1], that are 
      greater than key, to one position ahead 
      of their current position */
    while (j >= 0 && arr[j] > last) 
    { 
        arr[j+1] = arr[j]; 
        j--; 
    } 
    arr[j+1] = last; 
} 

Now, this uses a while loop at the end.... Can I do the same thing without using while loop and possibly implement while loop in another recursive function?

[lastchance]

void insertionSort( int A[], int n, int i = 1 )
{
   if ( i >= n ) return;
   rotate( upper_bound( A, A + i, A[i] ), A + i, A + i + 1 );
   insertionSort( A, n, i + 1 );
}

[ne555]

> Can I do the same thing without using while loop and possibly implement
> while loop in another recursive function?
so you want to do an `insert_sorted()' recursive function
just define the base and recursive cases

def insert_sorted(list, element):
	empty?(list):
		return (element)
	(rest | last) = list
	last < element:
		return append(list, element)
	else:
		return append(insert_sorted(rest, element), last)