Insertion Sort

Insertion Sort is the simplest sorting algorithm which sorts the array by shifting elements one by one.
It works the way we sort playing cards in our hands.
Characteristics:

• Simple implementation.
• Efficient for (quite) small data sets.
• More efficient in practice than most other simple quadratic (i.e., O(n*n)) algorithms such as selection sort or bubble sort.
• Stable; i.e., does not change the relative order of elements with equal keys.
• In-place; i.e., only requires a constant amount O(1) of additional memory space.

EXAMPLE

[Reference: wikipedia]

INSERTION SORT C-CODE

// C program to implement Insertion sort
#include <stdio.h>
 int main()
{
    int arr[] = {6, 3, 5, 2, 8, 10, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i, j, key;
    //Insertion Sort starts
    for (i = 1; i < n-1; i++)      
    {
         key=arr[i];
         for (j = i - 1; j >= 0 && arr[j] > key; j--)
         {
              a[j + 1] = arr[j];
          }
          arr[j + 1] = key;
    }
    //Insertion Sort ends
    printf("Sorted array: \n");
    for (int i=0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}

Output

Sorted array:
2  3  5  6  8  9  10

COMPLEXITY ANALYSIS

• Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
• Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
• Auxiliary Space Complexity: O(1). Only single extra memory space is required for "key" variable.

---