How to shuffle string characters to right and left until int.MaxValue?

You should be able to determine by the string's length how many iterations it will take before it's back to it's original sort order. Then take the modulus of the iteration count and the input count, and only iterate that many times.

For example, a string that is three characters will be back to it's original sort order in 2 iterations. If the input count was to do 11 iterations, we know that 11 % 2 == 1, so we only need to iterate one time.

Once you determine a formula for how many iterations it takes to reach the original sort order for any length of string, you can always reduce the number of iterations to that number or less.

Coming up with a formula will be tricky, however. A string with 14 characters takes 12 iterations until it matches itself, but a string with 15 characters only takes 4 iterations.

Therefore, a shortcut might be to simply start iterating until we reach the original sort order (or the specified count, whichever comes first). If we reach the count first, then we return that answer. Otherwise, we can determine the answer from the idea in the first paragraph - take the modulus of the input count and the iteration count, and return that answer.

This would require that we store the values from our iterations (in a dictionary, for example) so we can retrieve a specific previous value.

For example:

public static string ShuffleChars(string source, int count)
{
    string s = source;
    var results = new Dictionary<int, string>();

    for (int i = 0; i < count; i++)
    {
        s = string.Concat(s.Where((item, index) => index % 2 == 0)) +
            string.Concat(s.Where((item, index) => index % 2 != 0));

        // If we've repeated our original string, return the saved
        // value of the input count modulus the current iteration
        if (s == source)
        {
            return results[count % (i + 1) - 1];
        }
        // Otherwise, save the value for later
        else
        {
            results[i] = s;
        }
    }

    // If we get here it means we hit the requested count before
    // ever returning to the original sort order of the input
    return s;
}

Instead of creating new immutable strings on each loop, you could work with a mutable array of characters (char[]), and swap characters between places. This would be the most efficient in terms of memory consumption, but doing the swaps on a single array could be quite tricky. Using two arrays is much easier, because you can just copy characters from one array to the other, and at the end of each loop swap the two arrays.

One more optimization you could do is to work with the indices of the char array, instead of its values. I am not sure if this will make any difference in practice, since in modern 64 bit machines both char and int types occupy 8 bytes (AFAIK). It will surely make a difference on 32 bit machines though. Here is an implementation, with all these ideas put together:

public static string ShuffleChars(string source, int count)
{
    if (source == null) throw new ArgumentNullException(nameof(source));
    if (count < 0) throw new ArgumentOutOfRangeException(nameof(count));

    // Instantiate the two arrays
    int[] indices = new int[source.Length];
    int[] temp = new int[source.Length];

    // Initialize the indices array with incremented numbers
    for (int i = 0; i < indices.Length; i++)
        indices[i] = i;

    for (int k = 0; k < count; k++)
    {
        // Copy the odds to the temp array
        for (int i = 0, j = 0; j < indices.Length; i += 1, j += 2)
            temp[i] = indices[j];

        // Copy the evens to the temp array
        int lastEven = (indices.Length >> 1 << 1) - 1;
        for (int i = indices.Length - 1, j = lastEven; j >= 0; i -= 1, j -= 2)
                temp[i] = indices[j];

        // Swap the two arrays, using value tuples
        (indices, temp) = (temp, indices);
    }

    // Map the indices to characters from the source string
    return String.Concat(indices.Select(i => source[i]));
}