C# - MergeSort, running out of memory

Question

I implemented MergeSort algorithm that's used on a 100,000 integer file. It takes care of the sorting and collects inversions that are in the file. It works with small test arrays, but as soon as I plug in the actual file, I get out of memory error. How do I fix it? The error occurs during MergeSort, and the number of elements in my aux array is 12,500 Here's my code:

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Assignment_1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> data = File2Array("IntegerArray.txt");
            int[] unsorted = data.ToArray();
            List<string> inversions = new List<string>();
            Sort(ref unsorted, ref inversions);
            Console.WriteLine("number of inversions is: " + inversions.Count());
            Console.ReadLine();
        }

        public static void Sort(ref int[] unsorted, ref List<string>inversions)
        {
            int size = unsorted.Length;
            if (size == 1)
                return;
            int mid = size / 2;
            int leftSize = mid;
            int rightSize = size - leftSize;
            int[] left = new int[leftSize];
            int[] right = new int[rightSize];
            Array.Copy(unsorted, 0, left, 0, leftSize);
            Array.Copy(unsorted, mid, right, 0, rightSize);
            Sort(ref left, ref inversions);
            Sort(ref right, ref inversions);

            int[] aux = new int[leftSize + rightSize];
            for (int i = 0, j = 0, k = 0; k < aux.Length; k++)
            {
                if (left[i] < right[j])
                {
                    aux[k] = left[i++];
                    // if left array is exhausted, copy the remaining right array elements over
                    if (i == leftSize)
                    {
                        Array.Copy(right, j, aux, ++k, rightSize - j);
                        unsorted = aux;
                        break;
                    }
                }
                else
                {
                    int temp = i;
                    while (temp < leftSize)
                    {
                        inversions.Add(left[temp++] + "-" + right[j]);
                    }
                    aux[k] = right[j++];
                    if (j == rightSize)
                    {
                        Array.Copy(left, i, aux, ++k, leftSize - i);
                        unsorted = aux;
                        break;
                    }
                }
            }
        }

        public static List<int> File2Array(string file)
        {
            List<int> data = new List<int>();
            using (StreamReader reader = new StreamReader(file))
            {
                int line;
                do
                {
                    int.TryParse(reader.ReadLine(), out line);
                    data.Add(line);
                }
                while (!reader.EndOfStream);
            }
            return data;
        }
    }
}

Answer 1

Here's some code for you to look at.

This starts with recognizing that the file is already a collection of single elements. Therefore we can do the first grouping/sorting when we read the file. Since arrays are very impractical for this part I used Lists and then cast the return to int[][]

static int[][] makearrays(string filename)
{
    List<List<int>> outval = new List<List<int>>();
    using(StreamReader sr = new StreamReader(filename))
    {
        while(!sr.EndOfStream)
        {
            int a = 0, b = 0;
            a = int.Parse(sr.ReadLine());
            if(!sr.EndOfStream)
                b = int.Parse(sr.ReadLine());
            else
            {
                outval.Add(new List<int>() { a });
                break;
            }
            if(a > b)
                outval.Add(new List<int>() { b, a });
            else
                outval.Add(new List<int>() { a, b });

        }
    }
    return outval.Select(x => x.ToArray()).ToArray();
}

With this array we can start the rest of the grouping/sorting

This uses recursion but has a minimal memory footprint:

static int[][] dosort(int[][] input)
{
    if(input.Length == 1)
        return input;
    int i = 1, m = 0;
    for(; i < input.Length; i += 2)
    {
        int limit = Math.Min(input[i].Length, input[i - 1].Length);
        int[] temp = new int[input[i].Length + input[i - 1].Length];
        int j = 0, k = 0, l = 0;
        while(j < input[i].Length && k < input[i - 1].Length)
        {
            if(input[i][j] < input[i - 1][k])
            {
                temp[l++] = input[i][j++];
            }
            else
                temp[l++] = input[i - 1][k++];
        }
        while(l < temp.Length)
        {
            if(j < input[i].Length)
                temp[l++] = input[i][j++];
            if(k < input[i - 1].Length)
                temp[l++] = input[i - 1][k++];
        }
        input[m++] = temp;
    }
    if(input.Length % 2 == 1)
        input[m++] = input.Last();
    input = input.Take(m).ToArray();
    return dosort(input);
}

In my tests the 100000 element file was sorted in less than a quarter of a second, including reading it into memory.