テキストに書いてあったマージソートのアルゴリズムです。

        public void MargeSort(List<int> A)
        {
            List<int> C = new List<int>();
            for(int i = 0; i < A.Count; i++)
            {
                C.Add(0);
            }
            MargeSortSub(A, C, 0, A.Count);
        }

        public void MargeSortSub(List<int> A, List<int> C, int l, int r)
        {
            if(r - l == 1)
            {
                return;
            }

            int m = (l + r) / 2;
            MargeSortSub(A, C, l, m);
            MargeSortSub(A, C, m, r);

            int c1 = l;
            int c2 = m;
            int cnt = 0;

            while(c1 != m || c2 != r)
            {
                if (c1 == m)
                {
                    C[cnt] = A[c2];
                    c2++;
                }else if (c2 == r)
                {
                    C[cnt] = A[c1];
                    c1++;
                }else
                {
                    if(A[c1] <= A[c2])
                    {
                        C[cnt] = A[c1];
                        c1++;
                    }else
                    {
                        C[cnt] = A[c2];
                        c2++;
                    }
                }
                cnt++;
            }

            for(int i = 0; i < cnt; i++)
            {
                A[l + i] = C[i];
            }
        }