Sort an Array using Recursion

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;
}