Program.cs

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Order;
using BenchmarkDotNet.Running;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Runtime.Intrinsics;
using System.Runtime.Intrinsics.X86;

namespace FastInsertionSort
{
    class Program
    {
        static void Main(string[] args)
        {
            if (!Sse42.IsSupported) Console.WriteLine("SSE4.2 not supported");
            if (!Sse2.IsSupported) Console.WriteLine("SSE2 not supported");

            var a = new int[] { 5, 4, 3, 2, 1, 10 };
            var b = new int[] { 5, 4, 3, 2, 1, 10 };

            Console.WriteLine(string.Join(", ", a));
            InsertionSortBenchmark.BasicSort(ref a);
            Console.WriteLine(string.Join(", ", a));

            Console.WriteLine(string.Join(", ", b));
            InsertionSortBenchmark.SSE2Sort(ref b);
            Console.WriteLine(string.Join(", ", b));

            Console.ReadLine();

            BenchmarkRunner.Run<InsertionSortBenchmark>();
        }
    }

    [CoreJob]
    [MarkdownExporter]
    [Orderer(SummaryOrderPolicy.FastestToSlowest)]
    public class InsertionSortBenchmark
    {
        public IEnumerable<object> GetToOrder()
        {
            return new int[][]
            {
                Enumerable.Range(0, N).Shuffle().ToArray()
            };
        }

        [Params(10, 100, 300)]
        public int N;

        [ParamsSource(nameof(GetToOrder))]
        public int[] ToOrder;

        [Benchmark(Baseline = true)]
        public void Basic() => BasicSort(ref ToOrder);
        [Benchmark]
        public void SSE2() => SSE2Sort(ref ToOrder);

        public static void BasicSort(ref int[] toOrder)
        {
            for (int i = 1; i < toOrder.Length; i++)
            {
                var value = toOrder[i];
                var j = i;

                while (j > 0 && toOrder[j - 1] > value)
                {
                    toOrder[j] = toOrder[j - 1];
                    j = j - 1;
                }

                toOrder[j] = value;
            }
        }

        public static void SSE2Sort(ref int[] toOrder)
        {
            for (int i = 1; i < toOrder.Length; i++)
            {
                var value = toOrder[i];
                var j = i;
                bool done = false;
                if (Sse2.IsSupported)
                {
                    var valueVector = Vector128.Create(value, value, value, value);
                    while (j >= 4)
                    {
                        var vector = Vector128.Create(toOrder[j - 1], toOrder[j - 2], toOrder[j - 3], toOrder[j - 4]);
                        var resultVector = Sse2.CompareGreaterThan(vector, valueVector);

                        for (int k = 0; k < 4; k++)
                        {
                            if ((j - k) <= 0 || resultVector.GetElement(k) != -1)
                            {
                                done = true;
                                break;
                            }

                            toOrder[(j - k)] = toOrder[(j - k) - 1];
                        }
                        j = j - 4;
                    }
                }

                if (!done) // other didn't ran to completion and couldn't fit into Vector
                {
                    while (j > 0 && toOrder[j - 1] > value)
                    {
                        toOrder[j] = toOrder[j - 1];
                        j = j - 1;
                    }
                    toOrder[j] = value;
                }
            }
        }
    }
}