Problem Statement

Given an unsorted array of integers, sort the array using a recursive insertion approach. You are not allowed to use any built-in sort functions or non-recursive methods for sorting. Implement a function to recursively sort the array in ascending order.

Examples

Example 1:

Input: nums = [10, -1, 7, 3]
Output: [-1, 3, 7, 10]

Different Approaches

1️⃣ Recursion:

Intuition:

The goal is to sort an array using recursion by removing elements one-by-one and reinserting them into the sorted portion of the array. Each function serves a role in progressively building a sorted array from the last element backward:

1. Recursive Sorting with Reduction:
   1. Start by sorting the array without the last element, so we’re recursively shrinking the array.
   2. Once the smaller subarray is sorted, insert the last element in its correct position, maintaining the sorted order.
2. Insertion with Recursion:
   1. Inserting an element into a sorted array without directly using a loop.
   2. By recursively removing the last element and calling merging, we find the correct spot for the element being inserted and place the removed elements back in order.

Code:

#include <iostream>
#include <vector>

using namespace std;

void merging(vector<int>& arr, int last, int temp) {
    // Base case: if arr is empty or temp is greater than the last element in arr
    if (arr.size() == 0 || arr.back() <= temp) {
        arr.push_back(temp);  // Place temp in the correct position
        arr.push_back(last);   // Restore last element at the end
        return;
    }
    
    // Recursive case: remove last element and continue merging
    int veryLast = arr.back();
    arr.pop_back();
    merging(arr, veryLast, temp);

    // After placing temp, add veryLast back to its position
    arr.push_back(last);
}

void insert(vector<int>& arr, int temp) {
    // Base case: if array is empty, push the element
    if (arr.size() == 0 || arr.back() <= temp) {
        arr.push_back(temp);
        return;
    }

    // Remove last element and call merging to insert temp correctly
    int last = arr.back();
    arr.pop_back();
    merging(arr, last, temp);
}

void sort_helper(vector<int>& arr) {
    // Base case: if array has 0 or 1 element, it's already sorted
    if (arr.size() <= 1) {
        return;
    }

    // Remove last element to reduce the problem size
    int temp = arr.back();
    arr.pop_back();

    // Sort the remaining array recursively
    sort_helper(arr);

    // Insert the removed element back into sorted array
    insert(arr, temp);
}

void sort(vector<int>& arr) {
    sort_helper(arr);
}

int main() {
    vector<int> arr = {5, -1, 6, 2};
    sort(arr);

    cout << "Sorted array: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

OR

#include <iostream>
#include <vector>

using namespace std;

// Function to insert the last element into the sorted portion of the array
void resolve(vector<int>& arr, int lastElm) {
    // If the array is empty or the last element is less than or equal to lastElm,
    // then lastElm can be placed at the end of the array.
    if (arr.empty() || arr.back() <= lastElm) {
        arr.push_back(lastElm);  // Place lastElm in its correct position
        return;
    }
    
    // Remove the last element temporarily
    int top = arr.back();  // Store the last element
    arr.pop_back();        // Remove the last element from the array
    
    // Recursively call resolve to find the correct position for lastElm
    resolve(arr, lastElm);
    
    // After placing lastElm, restore the previously removed element (top) back
    arr.push_back(top);
}

// Function to sort the array recursively
void sort(vector<int>& arr) {
    // Base case: if the array is empty, return as it's already sorted
    if (arr.empty()) {
        return;
    }
    
    // Remove the last element from the array for sorting
    int lastElm = arr.back();  // Store the last element
    arr.pop_back();            // Remove it from the array
    
    // Recursively sort the remaining array
    sort(arr);
    
    // Insert the last element back into the sorted array
    resolve(arr, lastElm);
}

int main() {
    // Example array to sort
    vector<int> arr = {5, 10, 3, 7, 1};

    // Call the sort function to sort the array
    sort(arr);

    // Print the sorted array
    for (int elm : arr) {
        cout << elm << endl;  // Output each element of the sorted array
    }

    return 0;  // Indicate successful termination of the program
}

Complexity Analysis:

• Time Complexity: O(n^2)
  • Because each element may need to be shifted up to n times across the recursive calls.
• Space Complexity: O(n)
  • Due to recursive call stack depth.