ZetCode

C# external sort

last modified November 15, 2026

In this article we sort files that are larger than the available memory in C#. We split the file into sorted chunks, write them to temporary files, and merge them with a k-way merge built on PriorityQueue.

Sorting is arranging the elements of a collection in a specific order, for instance from the smallest to the largest. A sorting algorithm is the sequence of steps that produces this order.

External sort algorithm

An external sort sorts data that does not fit into memory. The most common variant is the external merge sort, which has two phases:

  1. The input is read in chunks that fit into memory. Each chunk is sorted in memory and written to a temporary file, called a run.
  2. All runs are merged at once. The merge keeps one current element from each run in a priority queue, writes the smallest one to the output, and replaces it with the next element from the same run.
PropertyValue
TimeO(n log n)
Memoryone chunk in the first phase, one line per run in the second
Disk I/Othe data is read twice and written twice
Stableif the chunk sort and the merge are stable

Merging k runs of total length n with a heap takes O(n log k) time. The Unix sort command and databases sorting large result sets use this algorithm.

K-way merge

The first example shows the merge phase on three sorted arrays in memory.

Program.cs
int[][] runs =
[
    [3, 14, 27, 40],
    [1, 9, 30],
    [5, 6, 22, 35, 41],
];

var pq = new PriorityQueue<int, int>();
int[] pos = new int[runs.Length];

for (int r = 0; r < runs.Length; r++)
{
    pq.Enqueue(r, runs[r][0]);
}

List<int> merged = [];

while (pq.TryDequeue(out int r, out int value))
{
    merged.Add(value);
    Console.WriteLine($"take {value,2} from run {r}");

    pos[r]++;

    if (pos[r] < runs[r].Length)
    {
        pq.Enqueue(r, runs[r][pos[r]]);
    }
}

Console.WriteLine(string.Join(" ", merged));

The priority queue holds the index of each run with the run's current element as the priority.

for (int r = 0; r < runs.Length; r++)
{
    pq.Enqueue(r, runs[r][0]);
}

At the start, the queue contains the first element of each run.

while (pq.TryDequeue(out int r, out int value))
{
    merged.Add(value);

TryDequeue removes the run with the smallest current element. The value is the next element of the output.

pos[r]++;

if (pos[r] < runs[r].Length)
{
    pq.Enqueue(r, runs[r][pos[r]]);
}

The run that provided the value moves to its next element. An exhausted run leaves the queue. The queue never holds more than one element per run.

$ dotnet run
take  1 from run 1
take  3 from run 0
take  5 from run 2
take  6 from run 2
take  9 from run 1
take 14 from run 0
take 22 from run 2
take 27 from run 0
take 30 from run 1
take 35 from run 2
take 40 from run 0
take 41 from run 2
1 3 5 6 9 14 22 27 30 35 40 41

Sorting a file of numbers

The next example generates a file with one million random numbers and sorts it, keeping at most 200,000 numbers in memory.

Program.cs
using System.Diagnostics;

Directory.CreateDirectory("demo");

var rnd = new Random(42);
using (var sw = new StreamWriter("demo/input.txt"))
{
    for (int i = 0; i < 1_000_000; i++)
    {
        sw.WriteLine(rnd.Next(1_000_000_000));
    }
}

Console.WriteLine($"input: {new FileInfo("demo/input.txt").Length:N0} bytes");

var watch = Stopwatch.StartNew();
List<string> chunks = SplitIntoSortedChunks("demo/input.txt", 200_000);

foreach (string c in chunks)
{
    Console.WriteLine($"{c}: {new FileInfo(c).Length:N0} bytes");
}

MergeChunks(chunks, "demo/output.txt");
Console.WriteLine($"sorted in {watch.ElapsedMilliseconds} ms");

var lines = File.ReadLines("demo/output.txt").Select(int.Parse);
Console.WriteLine($"lines: {lines.Count():N0}, sorted: {lines.Zip(lines.Skip(1)).All(p => p.First <= p.Second)}");
Console.WriteLine($"first: {string.Join(" ", lines.Take(3))}");

Directory.Delete("demo", true);

static List<string> SplitIntoSortedChunks(string path, int chunkSize)
{
    List<string> chunks = [];
    var buffer = new List<int>(chunkSize);

    foreach (string line in File.ReadLines(path))
    {
        buffer.Add(int.Parse(line));

        if (buffer.Count == chunkSize)
        {
            chunks.Add(WriteChunk(buffer, chunks.Count));
            buffer.Clear();
        }
    }

    if (buffer.Count > 0)
    {
        chunks.Add(WriteChunk(buffer, chunks.Count));
    }

    return chunks;
}

static string WriteChunk(List<int> buffer, int index)
{
    buffer.Sort();

    string name = $"demo/chunk{index}.txt";
    File.WriteAllLines(name, buffer.Select(x => x.ToString()));

    return name;
}

static void MergeChunks(List<string> chunks, string output)
{
    var readers = chunks.Select(c => new StreamReader(c)).ToArray();
    var pq = new PriorityQueue<int, int>();

    for (int i = 0; i < readers.Length; i++)
    {
        if (readers[i].ReadLine() is string line)
        {
            pq.Enqueue(i, int.Parse(line));
        }
    }

    using (var writer = new StreamWriter(output))
    {
        while (pq.TryDequeue(out int i, out int value))
        {
            writer.WriteLine(value);

            if (readers[i].ReadLine() is string line)
            {
                pq.Enqueue(i, int.Parse(line));
            }
        }
    }

    foreach (var r in readers)
    {
        r.Dispose();
    }
}

The program works in the demo directory, which it deletes at the end.

foreach (string line in File.ReadLines(path))
{
    buffer.Add(int.Parse(line));

    if (buffer.Count == chunkSize)
    {
        chunks.Add(WriteChunk(buffer, chunks.Count));
        buffer.Clear();
    }
}

File.ReadLines reads the file lazily, line by line. When the buffer is full, it is sorted and written to a chunk file. The last, possibly smaller, chunk is written after the loop.

var readers = chunks.Select(c => new StreamReader(c)).ToArray();
var pq = new PriorityQueue<int, int>();

In the merge phase, all chunk files are open at the same time. Each reader needs only a small buffer, so even hundreds of runs take little memory.

if (readers[i].ReadLine() is string line)
{
    pq.Enqueue(i, int.Parse(line));
}

After writing a value, we read the next line from the same chunk. At the end of the chunk, ReadLine returns null and the chunk is not enqueued again.

var lines = File.ReadLines("demo/output.txt").Select(int.Parse);
Console.WriteLine($"lines: {lines.Count():N0}, sorted: {lines.Zip(lines.Skip(1)).All(p => p.First <= p.Second)}");

We verify that the output has one million lines and that each number is not greater than the next one. The check streams the file without loading it.

$ dotnet run
input: 9,888,677 bytes
demo/chunk0.txt: 1,977,717 bytes
demo/chunk1.txt: 1,977,747 bytes
demo/chunk2.txt: 1,977,684 bytes
demo/chunk3.txt: 1,977,764 bytes
demo/chunk4.txt: 1,977,765 bytes
sorted in 383 ms
lines: 1,000,000, sorted: True
first: 1739 2900 4457

Generic and stable external sort

The next example sorts lines of text with any comparer. It keeps the input order of lines that compare as equal and deletes its temporary files.

Program.cs
Directory.CreateDirectory("demo");

File.WriteAllLines("demo/words.txt",
[
    "sky", "Apple", "forest", "cup", "apple", "Sky", "war", "Cup",
    "ocean", "APPLE", "book", "SKY", "cloud", "Forest",
]);

ExternalSort("demo/words.txt", "demo/sorted.txt", 4, StringComparer.OrdinalIgnoreCase);

Console.WriteLine(string.Join(" ", File.ReadLines("demo/sorted.txt")));
Console.WriteLine($"files left: {Directory.GetFiles("demo").Length}");

Directory.Delete("demo", true);

static void ExternalSort(string input, string output, int chunkSize, IComparer<string> cmp)
{
    List<string> chunks = [];

    foreach (string[] chunk in File.ReadLines(input).Chunk(chunkSize))
    {
        string name = Path.Combine(Path.GetDirectoryName(output)!, $"chunk{chunks.Count}.tmp");
        File.WriteAllLines(name, chunk.OrderBy(s => s, cmp));
        chunks.Add(name);
    }

    var readers = chunks.Select(c => new StreamReader(c)).ToList();

    try
    {
        var order = Comparer<(string Line, int Chunk)>.Create((a, b) =>
        {
            int res = cmp.Compare(a.Line, b.Line);
            return res != 0 ? res : a.Chunk.CompareTo(b.Chunk);
        });

        var pq = new PriorityQueue<int, (string, int)>(order);

        for (int i = 0; i < readers.Count; i++)
        {
            if (readers[i].ReadLine() is string line) pq.Enqueue(i, (line, i));
        }

        using var writer = new StreamWriter(output);

        while (pq.TryDequeue(out int i, out var top))
        {
            writer.WriteLine(top.Item1);

            if (readers[i].ReadLine() is string line) pq.Enqueue(i, (line, i));
        }
    }
    finally
    {
        foreach (var r in readers) r.Dispose();
        foreach (string c in chunks) File.Delete(c);
    }
}

We sort words case-insensitively with chunks of four lines, so the fourteen words are split into four runs.

foreach (string[] chunk in File.ReadLines(input).Chunk(chunkSize))

The LINQ Chunk method splits the lazy sequence of lines into arrays of the given size.

File.WriteAllLines(name, chunk.OrderBy(s => s, cmp));

Each chunk is sorted with the stable OrderBy.

int res = cmp.Compare(a.Line, b.Line);
return res != 0 ? res : a.Chunk.CompareTo(b.Chunk);

The priority is a tuple of the line and the chunk index. When two lines are equal, the line from the earlier chunk goes first, and earlier chunks contain earlier lines of the input. Together with the stable chunk sort, this makes the whole sort stable: Apple, apple and APPLE are in the input order.

finally
{
    foreach (var r in readers) r.Dispose();
    foreach (string c in chunks) File.Delete(c);
}

The finally block closes the readers and deletes the chunk files even if the merge fails. Only the input and the output remain in the directory.

$ dotnet run
Apple apple APPLE book cloud cup Cup forest Forest ocean sky Sky SKY war
files left: 2

Sorting with limited memory

In the last example, we sort ten million numbers, a file of about 100 MB, in memory and with an external sort. The program creates the file on the first run.

benchmark.cs
#:property PublishAot=false

using System.Diagnostics;

const string Input = "numbers.txt";
const string Output = "sorted.txt";

if (!File.Exists(Input))
{
    var rnd = new Random(42);
    using var sw = new StreamWriter(Input);

    for (int i = 0; i < 10_000_000; i++) sw.WriteLine(rnd.Next());
}

string mode = args.Length > 0 ? args[0] : "memory";
var watch = Stopwatch.StartNew();

try
{
    if (mode == "external") ExternalSort();
    else InMemorySort();

    Console.WriteLine($"{mode}: {watch.ElapsedMilliseconds} ms");
}
catch (OutOfMemoryException)
{
    Console.WriteLine($"{mode}: out of memory after {watch.ElapsedMilliseconds} ms");
}

static void ExternalSort()
{
    var chunks = new List<string>();

    foreach (string[] chunk in File.ReadLines(Input).Chunk(500_000))
    {
        int[] nums = Array.ConvertAll(chunk, int.Parse);
        Array.Sort(nums);

        string name = $"chunk{chunks.Count}.tmp";
        File.WriteAllLines(name, nums.Select(n => n.ToString()));
        chunks.Add(name);
    }

    var readers = chunks.Select(c => new StreamReader(c)).ToArray();
    var pq = new PriorityQueue<int, int>();

    for (int i = 0; i < readers.Length; i++)
    {
        pq.Enqueue(i, int.Parse(readers[i].ReadLine()!));
    }

    using (var writer = new StreamWriter(Output))
    {
        while (pq.TryDequeue(out int i, out int value))
        {
            writer.WriteLine(value);

            if (readers[i].ReadLine() is string line) pq.Enqueue(i, int.Parse(line));
        }
    }

    foreach (var r in readers) r.Dispose();
    foreach (string c in chunks) File.Delete(c);
}

static void InMemorySort()
{
    List<int> nums = [.. File.ReadLines(Input).Select(int.Parse)];
    nums.Sort();
    File.WriteAllLines(Output, nums.Select(n => n.ToString()));
}

The in-memory version loads all numbers into a list; the external version sorts chunks of 500,000 numbers.

catch (OutOfMemoryException)
{
    Console.WriteLine($"{mode}: out of memory after {watch.ElapsedMilliseconds} ms");
}

We catch the exception that is thrown when the program needs more memory than it is allowed to use.

The DOTNET_GCHeapHardLimit environment variable limits the managed heap, here to 64 MB (0x4000000 bytes). Ten million integers take 40 MB, and the list grows by doubling its internal array, so the in-memory sort fails. The external sort finishes within the limit. It is slower, because it parses and writes every number twice.

$ dotnet run -c Release benchmark.cs
memory: 2317 ms
$ export DOTNET_GCHeapHardLimit=0x4000000
$ dotnet run -c Release benchmark.cs
memory: out of memory after 791 ms
$ dotnet run -c Release benchmark.cs external
external: 4070 ms

Source

PriorityQueue<TElement, TPriority> class
File.ReadLines method
Runtime configuration options for garbage collection

In this article we have sorted files larger than memory with an external merge sort in C#. The merge phase is described in more detail in the merge sort article.

Other sorting articles in C#:

Author

I am Jan Bodnar, a programmer and technical writer. I have been writing programming tutorials at ZetCode since 2007 and have published eight e-books. See about the author.

List all C# tutorials.