Problem Statement

You are given an unsorted array of integers. Your task is to sort the array in ascending order using recursion. You cannot use loops or built-in sort functions, and you must use only recursive calls to achieve the sorted array.

Examples

Example 1:

Input: arr = [3, 1, 4, 1, 5]
Output: [1, 1, 3, 4, 5]

Example 2:

Input: arr = [10, 2, 8, 6, 4]
Output: [2, 4, 6, 8, 10]

Different Approaches

1️⃣ Recursion:

#include <iostream>
#include <vector>
using namespace std;

// Function to insert an element into a sorted array
void insertSorted(vector<int>& arr, int value) {
    // Base case: if the array is empty or the value is greater than the last element, append it
    if (arr.empty() || arr.back() <= value) {
        arr.push_back(value);
        return;
    }

    // Remove the last element
    int last = arr.back();
    arr.pop_back();

    // Recursive call to insert value in the smaller array
    insertSorted(arr, value);

    // Put the last element back
    arr.push_back(last);
}

// Recursive function to sort the array
void sortArray(vector<int>& arr) {
    // Base case: if the array has 0 or 1 elements, it's already sorted
    if (arr.size() <= 1) {
        return;
    }

    // Remove the last element
    int last = arr.back();
    arr.pop_back();

    // Recursive call to sort the remaining array
    sortArray(arr);

    // Insert the removed element back into the sorted array
    insertSorted(arr, last);
}

int main() {
    vector<int> arr = {3, 1, 4, 1, 5};

    // Sort the array
    sortArray(arr);

    // Print the sorted array
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}