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:
- 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.
- 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.
| Property | Value |
|---|---|
| Time | O(n log n) |
| Memory | one chunk in the first phase, one line per run in the second |
| Disk I/O | the data is read twice and written twice |
| Stable | if 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.
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.
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.
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.
#: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#:
- Bubble sort
- Selection sort
- Insertion sort
- Shell sort
- Merge sort
- Quick sort
- Heap sort
- Counting sort
- Radix sort
- Bucket sort
- Array.Sort and Span.Sort
- Stable sorting
- Binary search
- Introsort
- Quickselect
- Timsort
Author
List all C# tutorials.