"Breaking out" elements from an array
So far my tests indicate that the performance is slightly better in the larger test cases because there is no hashing involved when accessing elements in deleteStatusArray. There are also no array copy operations.

public static void ZRemoveIndex&lt;T&gt;(this T[] array, int[] indices, out T[] rest, out T[] removed)
{
    int arrayLength = array.Length;
    int indicesLength = indices.Length;

    if (indicesLength == 0 || arrayLength == 0)
    {
        rest = array;
        removed = new T[0];
        return;
    }

    rest = new T[arrayLength - indicesLength];
    removed = new T[indicesLength];
    //memo to remember which array indices are removed
    //all elements will be false by default
    var deleteStatusArray = new bool[array.Length];

    foreach (var removeIndex in indices)
    {
        //mark index that should be considered deleted
        deleteStatusArray[removeIndex] = true;
    }

    var notRemovedCounter = 0;
    var removedCounter = 0;
    for (int i = 0; i &lt; array.Length; i++)
    {
        if(!deleteStatusArray[i])
            rest[notRemovedCounter++]= array[i];
        else
            removed[removedCounter++] = array[i];
    }
}