insertion-sort.cpp

#include<iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    int sortedArr[n];

    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sortedArr[0] = arr[0];
    for(int i = 0; i < n; i++) {
        if ((i + 1) < n && sortedArr[i] <= arr[i+1]) {
            sortedArr[i + 1] = arr[i + 1];
            continue;
        } else {
            for (int j = i; j > -1; j--) {
                if ((i + 1) < n && sortedArr[j] > arr[i+1]) {
                    int temp = sortedArr[j];
                    sortedArr[j] = arr[i+1];
                    sortedArr[j + 1] = temp;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << sortedArr[i] << " ";
    }
}