Recursive permutation of an array
permutations[count] = Arrays.copyOf(array, array.length);
        return count + 1;



Here you are copying the array into the permutations array after permuting the array itself.  This is why you have to keep making copies of the array.  

        return count;


If you instead do nothing in this case, you can change 


    else 
    {
        for (int i = midStart; i &lt; array.length; i++) 
        {
            T temp = array[i];
            array[i] = array[midStart];
            array[midStart] = temp;
            count = permute(permutations, array, midStart + 1, count);
        }
        return count;
    }



to copy the array before recursing instead.

        count = permute(permutations, array, midStart + 1, count);
        for (int i = midStart+1; i &lt; array.length; i++) 
        {
            permutations[count] = Arrays.copyOf(array, array.length);
            permutations[count][i] = array[midStart];
            permutations[count][midStart] = array[i];
            count = permute(permutations, permutations[count], midStart + 1, count + 1);
        }

        return count;


Now you never change the original array and you don't have to do any extraneous copies.  A side effect of this is that you don't need a temporary variable to do the swap either.  

Note that I also changed the for loop not to do the no-op swap at the beginning.  This was necessary since we don't want to copy in that case.  

We're now one copy short, so change 


public static void &lt;T&gt; permute (T[][] permutations, T[] array)
{
    if (permutations.length != factorial(array.length))
        throw new IllegalArgumentException();
    permute(permutations, array, 0, 0);
}



to

public static &lt;T&gt; void permute (T[][] permutations, T[] array)
{
    if (permutations.length != factorial(array.length)) {
        throw new IllegalArgumentException();
    }

    permutations[0] = Arrays.copyOf(array, array.length);
    permute(permutations, array, 0, 1);
}