Fastest way to move a part of an array to the right

Question

I need to "insert" an element at the given index in a small array. That is, to move all elements with greater indices 1 place to the right. What is the fastest way to do that in .NET?

NOTE: I added my own answer, but I am still looking for an explanation and faster alternatives.

EDIT: I do need an array, not a List<T> and not a linked list.

UPDATE: Since I didn't get an explanation of strange performance results, I've asked that question separately: Why is copying references to strings much slower than copying ints (but vice versa for Array.Copy())?

Answer 1

There are two obvious approaches: use Array.Copy and copy elements one by one:

private static void ElementByElement<T>(T[] arg, int start) {
    for (int i = arg.Length - 1; i > start; i--) {
        arg[i] = arg[i - 1];
    }
}

private static T BuiltInCopy<T>(T[] arg, int start) {
    Array.Copy(arg, start, arg, start + 1, arg.Length - start - 1);
    return arg[0];            
}

On one hand, List<T> insert uses Array.Copy. On the other, Array.Copy is non-generic and can do a lot of extra work: http://msdn.microsoft.com/en-us/library/z50k9bft.aspx

I expected Array.Copy to be faster. However, the results of this MiniBench test surprised me.

internal class Program {
    private static int smallArraySize = 32;

    public static void Main(string[] args) {
        BenchArrayCopy();
    }

    private static void BenchArrayCopy() {
        var smallArrayInt = new int[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayInt[i] = i;

        var smallArrayString = new string[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayString[i] = i.ToString();

        var smallArrayDateTime = new DateTime[smallArraySize];
        for (int i = 0; i < smallArraySize; i++)
            smallArrayDateTime[i] = DateTime.Now;

        var moveInt = new TestSuite<int[], int>("Move part of array right by 1: int")
            .Plus(BuiltInCopy, "Array.Copy()")
            .Plus(ElementByElement, "Element by element in a for loop")
            .RunTests(smallArrayInt, 0);

        var moveString = new TestSuite<string[], string>("Move part of array right by 1: string")
            .Plus(BuiltInCopy, "Array.Copy()")
            .Plus(ElementByElement, "Element by element in a for loop")
            .RunTests(smallArrayString, "0");

        var moveDT = new TestSuite<DateTime[], DateTime>("Move part of array right by 1: DateTime")
            .Plus(BuiltInCopy, "Array.Copy()")
            .Plus(ElementByElement, "Element by element in a for loop")
            .RunTests(smallArrayDateTime, smallArrayDateTime[0]);

        moveInt.Display(ResultColumns.All, moveInt.FindBest());
        moveString.Display(ResultColumns.All, moveInt.FindBest());
        moveDT.Display(ResultColumns.All, moveInt.FindBest());
    }

    private static T ElementByElement<T>(T[] arg) {
        int start = 8;
        for (int i = smallArraySize - 1; i > start; i--) {
            arg[i] = arg[i - 1];
        }
        return arg[0];
    }

    private static T BuiltInCopy<T>(T[] arg) {
        int start = 8;
        int length = smallArraySize - start - 1;
        Array.Copy(arg, start, arg, start + 1, length);
        return arg[0];            
    }
}

Here are the results from two runs:

f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()                     568475865 0:31.606 1,73
Element by element in a for loop 980013061 0:31.449 1,00

============ Move part of array right by 1: string ============
Array.Copy()                     478224336 0:31.618 2,06
Element by element in a for loop 220168237 0:30.926 4,38

============ Move part of array right by 1: DateTime ============
Array.Copy()                     382906030 0:27.870 2,27
Element by element in a for loop 458265102 0:29.239 1,99


f:\MyProgramming\TimSort\Benchmarks\bin\Release>Benchmarks.exe
============ Move part of array right by 1: int ============
Array.Copy()                     500925013 0:28.514 1,76
Element by element in a for loop 988394220 0:31.967 1,00

============ Move part of array right by 1: string ============
Array.Copy()                     483178262 0:30.048 1,92
Element by element in a for loop 193092931 0:27.642 4,43

============ Move part of array right by 1: DateTime ============
Array.Copy()                     450569361 0:30.807 2,11
Element by element in a for loop 568054290 0:31.385 1,71

That is, for int and DateTime ElementByElement is significantly faster; while for string BuiltInCopy is over twice as fast as ElementByElement (and twice as slow as ElementByElement for int). I'd expect the results for int and string to be very similar on a 32-bit machine, since a reference to string on the stack is the same size as an int and no operations other than reading and writing stack memory should be involved.