mergesort - при незначительном изменении выдает SystemInvalidOperationException

Question

В моей программе произошла очень странная вещь. Вот упрощенный код.

class Program
{
    static void Main(string[] args)
    {
        ArrayList numbers = new ArrayList();
        numbers.Add(1);
        numbers.Add(3);
        numbers.Add(4);
        numbers.Add(2);

        var it = Sorts.MergeSort((ArrayList)numbers.Clone());
        Sorts.PrintArray(it, "mergesort");

        Console.WriteLine("DONE");
        Console.ReadLine();
    }
}

public static class Sorts
{
    public static ArrayList BubbleSort(ArrayList numbers)
    {

        bool sorted = true;
        for (int i = 0; i < numbers.Count; i++)
        {

            for (int j = 1; j < numbers.Count; j++)
            {
                if ((int)numbers[j - 1] > (int)numbers[j])
                {
                    int tmp = (int)numbers[j - 1];
                    numbers[j - 1] = numbers[j];
                    numbers[j] = tmp;
                    sorted = false;
                }
            }
            if (sorted)
            {
                return numbers;
            }
        }
        return numbers;
    }

    public static ArrayList MergeSort(ArrayList numbers, int switchLimit = 3)
    {

        //if I use this if - everything works
        if (numbers.Count <= 1)
        {
           // return numbers;
        }

        //the moment I use this condition - it throws SystemInvalidOperationException in function Merge in the line of a "for"-loop
        if (numbers.Count <=switchLimit)
        {
              return Sorts.BubbleSort(numbers);
        }

        ArrayList ret = new ArrayList();
        int middle = numbers.Count / 2;

        ArrayList L = numbers.GetRange(0, middle);
        ArrayList R = numbers.GetRange(middle, numbers.Count - middle);
        L = MergeSort(L);
        R = MergeSort(R);

        return Merge(L, R);
    }

    private static ArrayList Merge(ArrayList L, ArrayList R)
    {

        ArrayList ret = new ArrayList();

        int l = 0;
        int r = 0;
        for (int i = 0; i < L.Count + R.Count; i++)
        {
            if (l == L.Count)
            {
                ret.Add(R[r++]);

            }
            else if (r == R.Count)
            {
                ret.Add(L[l++]);
            }

            else if ((int)L[l] < (int)R[r])
            {
                ret.Add(L[l++]);
            }
            else
            {
                ret.Add(R[r++]);
            }
        }

        return ret;
    }

    //---------------------------------------------------------------------------------

    public static void PrintArray(ArrayList arr, string txt = "", int sleep = 0)
    {
        Console.WriteLine("{1}({0}): ", arr.Count, txt);
        for (int i = 0; i < arr.Count; i++)
        {
            Console.WriteLine(arr[i].ToString().PadLeft(10));
        }
        Console.WriteLine();
        System.Threading.Thread.Sleep(sleep);
    }
}

Проблема с моей функцией Sorts.MergeSort. Когда я использую его нормально (взгляните на первое условие if в функции - все работает отлично. Но в тот момент, когда я хочу, чтобы он переключился на пузырьковую сортировку с меньшим вводом (второе условие if в функции), он вызывает исключение SystemInvalidOperationException. Я понятия не имею, в чем проблема. Вы видите это? Благодарю. :) Замечание: само пузырьковое сортирование работает, поэтому проблем такого рода не должно быть ...

Answer 1

Проблема заключается в использовании GetRange:

Этот метод не создает копии элементов.Новый ArrayList - это только окно просмотра исходного ArrayList.Однако все последующие изменения в исходном ArrayList должны быть сделаны через это окно просмотра ArrayList.Если изменения вносятся непосредственно в исходный ArrayList, окно представления ArrayList становится недействительным, и любые операции над ним возвращают исключение InvalidOperationException.

Вы создаете два представления для исходного ArrayList и пытаетесьработать с ними обоими - но когда одно представление изменяет базовый список, другое представление фактически становится недействительным.

Если вы измените код для создания копий подсписков - или если вы работаетенепосредственно с исходным списком в указанных пределах - тогда я считаю, что он будет работать нормально.

(Как отмечалось в комментариях, я бы также настоятельно рекомендовал использовать общие коллекции.)

Вот короткая, но полная программа, которая демонстрирует проблему, с которой вы столкнулись:

using System;
using System.Collections;

class Program
{
    static void Main()
    {
        ArrayList list = new ArrayList();
        list.Add("a");
        list.Add("b");

        ArrayList view1 = list.GetRange(0, 1);
        ArrayList view2 = list.GetRange(1, 1);

        view1[0] = "c";
        Console.WriteLine(view2[0]); // Throws an exception
    }
}

Answer 2

в этой строке R = MergeSort(R); вы изменяете диапазон чисел, представленных L. Это делает недействительным L. Извините, я должен идти, поэтому больше не могу объяснять.