Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than the similar merge sort.

#include<stdio.h>
void insertionSort(int[], int);
int main(){
    int n, arr[50];
    printf("Enter the number of elements: ");
    scanf("%d",&n);
    printf("Enter %d elements: ",n);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    insertionSort(arr, n);
    printf("Sorted array: ");
    for(int i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

void insertionSort(int arr[], int n){
    int i, j, key;
    for(i=1;i<n;i++){
        key = arr[i];
        j = i-1;
        while(j>=0 && arr[j]>key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

Sample Input and Output:
Enter the number of elements: 7
Enter 7 elements: 6 3 12 9 15 21 18
Sorted array: 3 6 9 12 15 18 21