Insertion Sort - The Sorting Algorithm Family Reunion

The eldest child of the family, Insertion Sort has a good life.

Between working as an accountant at a high-powered law firm and her indelible engagement and eventual marriage to loving husband Quick Sort, Insertion Sort (Innie, as she is known to her friends) has a life dreamt of by many. The family relies on her smarts to keep their financial lives balanced, and by all accounts she does an amazing job of this.

After all, who'd notice that, occasionally, a very small percentage of it gets, ahem, "redirected" to other causes. The parents don't even mind all that much.

Innie can't help but feel some jealousy toward her sister Heap Sort. She never got Heapy's culinary skills, and so feels that her parents are slightly disappointed in her, though she knows they would never show it.

She is consistently the most well-off member of her family, and she makes sure they know all about it with flashy jewelry and designer clothes and expensive cars, hoping against vain hope that this makes her more "worthy" in her parents' eyes.  

The Rundown

• Created By: Unknown
• Type: Insertion
• Stable? YES
• Best-Case:  O(n)
• Average-Case:  O(n²)
• Worst-Case:  O(n²)
• Space Complexity: O(n)
• Sample Project: Over on GitHub

exceptionnotfound/SortExtravaganzaCSharp

Lots of example sorting algorithms, from a family reunion. - exceptionnotfound/SortExtravaganzaCSharp

GitHubexceptionnotfound

Algorithm

1. FOR each value in the array
2. STORE the current value in a variable.
3. WHILE we are pointing to a valid value...
4. ...IF the current value is less than the value we are point at
5. ...THEN move the pointed-at value up one space, and store the current value at the pointed-at position.

Visualization

You may notice a "stair step" effect in the above visualization; that is, values progressively "stepping" down to the left of the frame. This stair stepping represents the comparison happening during steps 4 and 5 of the algorithm above; Insertion Sort moves each value up one step if it is greater than the current value.

Also, as with the previous entries in this series, check out the very cool "visualization and audibilization" of Insertion Sort from YouTube:

C# Implementation

class InsertionSort
{
    static void Main(string[] args)
    {
        int[] array = new int[15] { 55, 97, 76, 60, 4, 18, 37, 34, 88, 51, 43, 49, 19, 12, 63 };
        Console.WriteLine("Insertion Sort");

        CommonFunctions.PrintInitial(array);

        //1. For each value in the array...
        for (int i = 1; i < array.Length; ++i)
        {
            //2. Store the current value in a variable.
            int currentValue = array[i];
            int pointer = i - 1;

            //3. While we are pointing to a valid value...
            //4. If the current value is less than the
            //   value we are pointing at...
            while (pointer >= 0 && array[pointer] > currentValue)
            {
                //5. Then move the pointed-at value up one space, and store the
                //   current value at the pointed-at position.
                array[pointer + 1] = array[pointer];
                pointer = pointer - 1;
            }
            array[pointer + 1] = currentValue;
        }

        CommonFunctions.PrintFinal(array);

        Console.ReadLine();
    }
}

Time and Space Complexity

As with most sorting algorithms, the best-case scenario for Insertion Sort is that the array is already sorted; in this case, the algorithm has O(n) time, because it still needs to iterate over the entire array even though it won't do any swaps.  

But in the average and worst cases, Insertion Sort doesn't fare too well with its O(n²) complexity. There are a good many sorting algorithms (several of which we will see later in this series) which are substantially more efficient in these situations.

That said, insertion sort has a couple of things going for it, apart from the cushy job and respect from the family. For starters, it's relatively easy to implement and very efficient on data sets that are already mostly sorted, so in some scenarios it actually performs better than algorithms such as QuickSort. Further, it requires very little addition space to perform the algorithm. In short, it's a very useful learning algorithm, and has a few practical applications as well.

Summary

Insertion Sort is an algorithm that works best on mostly-sorted data, and is a bit inefficient for large unsorted collections. That said, it's very useful for small data, being easy to implement and analyze. Just watch it around your money.

Next in this series is the quiet, unassuming Shell Sort, the son of Insertion Sort. He'd much rather be reading.

Shell Sort in C#

Shell Sort is the unassuming, quiet type. The late-teens son of high-achievingInsertion Sort and Quick Sort, Shell Sort would much rather just curl up alonewith a good sci-fi/fantasy book and sip hot cocoa. He’s a straight-A high school senior who really doesn’t understand why he has tobe at th…

Exception Not FoundMatthew Jones

Don't forget to check out the sample project over on GitHub!

Happy Coding!