Insertion sort in recursion

#1

Please let me know why the code isn’t working , I tried recursion approach.

#2

@jayasmit98,
The iterative algo of insertion sorting is this :-

// Sort an arr[] of size n
insertionSort(arr, n) 
    Loop from i = 1 to n-1.
       a) Pick element arr[i] and insert
          it into sorted sequence arr[0..i-1]

Now , you we notice that we maintain the sorted subarray a[0…i-1] and then insert ith element to its correct position . but in your code there are two main flaws

  1. you are sorting the prefix subarray after inserting the ith element
  2. you are not maintaining the sorted array , as in your code a[j+1]=a[j]; should be swap(a[j+1],a[j])

So what you need to do is :-
we keep processed elements sorted and insert new elements one by one in the inserted array.

Recursion Idea.

  1. Base Case: If array size is 1 or smaller, return.
  2. Recursively sort first n-1 elements.
  3. Insert last element at its correct position in sorted array.

try to implement this your self , if you run into some problem then refer this ->

In case of any doubt feel free to ask :slight_smile:
Mark your doubt as RESOLVED if you got the answer

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.