Insertion sort

Best Case: n

Average Case: n2

Worst Case: n2

Stable: Yes

Insertion sort is a very simple algorithm that builds the list one at a time. Not very efficient when compared to other algorithms like quick sort or merge sort. It is stable and incredibly small making it possible to build with few lines of code.

  • Good for small data sets
  • Good for data sets that are sorted slightly
  • Uses little memory
  • Can sort the data as it recieves it

C++/C example

   
    void InsertionSort(int A[], int size) {

    int i, k, j;

    for (i = 1; i < size; i++)
    {
        k = A[i];
        j = i-1;
        
        //moves the elements abpve the key if they are a greater value
        while (j >= 0 && A[j] > k) {
            A[j+1] = A[j];
            j = j-1;
        }
        A[j+1] = k;
    }
}


int main()
{
    double random;

    //create an empty array with 100 elements
    int A[100000];

    //creating random number generator
    srand (time(NULL));

    //get the size of array
    int size = (sizeof(A)/sizeof(A[0]));

    //loops through and inserts into array with a random int between 1-1000
    for (int i = 0; i < size; i++)
    {
        random = rand() % 10001 + 0;
        A[i] = random;
    }

    //begin sorting
    InsertionSort(A, size);
    //print through sorted array
    for (int i = 0; i < size; i++)
    {
        std::cout << A[i] << std::endl;
    }

    return 0;
}           
                

Summary

Not a fast algorithm but because of its low memory usage can make it ideal for older hardware. Also rather flexible with how it can be used it's long execution time is off puitting however.