A high-performance C program that reads hundreds of millions of integers from multiple files, sorts them in parallel using POSIX threads and Mergesort, and writes the result to a single sorted output file — all with a pipeline optimized at every stage.

500,000,000 integers sorted in under 20 seconds with 12 sorter threads.

• Overview
• Architecture
• Performance Results
• Optimizations
  • Reader
  • Writer
• How to Run
• Test Configuration
• Author

This program solves a classic systems programming challenge at scale:

1. Read — distribute input files across reader threads, each parsing integers from disk as fast as possible
2. Sort — merge all data into a single array, split it evenly across sorter threads, and sort in parallel using Mergesort
3. Write — merge all sorted subarrays into a single output file using a min-heap for O(N log T) k-way merge

This is v2 of the project — a full refactor from the first implementation, featuring better code organization, reduced complexity, and major performance optimizations throughout the entire pipeline.

┌─────────────────────────────────────────────┐
│              Input Files (N files)           │
└────────────────┬────────────────────────────┘
                 │  distributed equally
        ┌────────▼────────┐
        │  Reader Threads  │  (T threads, each reads a file subset)
        │  fread + manual  │  ← buffered I/O, 4MB block reads
        │  integer parser  │
        └────────┬────────┘
                 │  merge into single array
        ┌────────▼────────┐
        │  Sorter Threads  │  (T threads, each sorts N/T integers)
        │    Mergesort     │  ← in-place parallel sort
        └────────┬────────┘
                 │  sorted subarrays
        ┌────────▼────────┐
        │  Writer (1 thd)  │  ← min-heap k-way merge
        │  fast_itoa +     │  ← buffered fwrite, no fprintf
        │  fwrite buffer   │
        └────────┬────────┘
                 │
        ┌────────▼────────┐
        │   Output File    │
        └─────────────────┘

All tests run on 500,000,000 integers spread across 5 files (100M integers each).

Case 1 (1 thread):   ████████████████████████████████████████  70.21s  (1.0×)
Case 2 (2 threads):  ████████████████████████  41.44s  (1.7×)
Case 3 (4 threads):  ████████████████  27.87s  (2.5×)
Case 4 (6 threads):  █████████████  22.43s  (3.1×)
Case 5 (12 threads): ███████████  19.35s  (3.6×)

• Sorter scales nearly linearly with threads — doubling threads roughly halves sort time (56s → 28s → 14s → 10s → 6.5s)
• Reader also benefits from parallelism but is I/O-bound, so gains taper off after 4–5 threads
• Writer time stays nearly constant (~10–11s) across all cases — it is the irreducible sequential bottleneck, writing 500M integers to disk
• Sorter threads can exceed reader threads — since there are only 5 input files, Cases 4 and 5 (-t 6, -t 12) cap reader threads at 5 but still spin up the full T sorter threads, maximizing CPU utilization during the sort phase

The reader was rewritten from a fscanf-based approach to a high-throughput buffered streaming parser.

// ❌ Old — one function call per integer
while (fscanf(fp, "%d", &num) == 1) { ... }

// ✅ New — bulk block reads into a 4MB buffer
while ((bytes = fread(buffer, 1, BUF_SIZE, file)) > 0) { ... }

Block reads reduce system call overhead by orders of magnitude and maximize disk throughput.

// ✅ Simple, branch-predictable, CPU-efficient
num = num * 10 + (c - '0');

Eliminates all the overhead inside fscanf: format parsing, type dispatch, and internal locking.

A lightweight state machine handles number boundaries correctly across buffer splits:

if (c >= '0' && c <= '9') {
    num = num * 10 + (c - '0');
    reading = 1;
} else if (reading) {
    array[count++] = num;
    num = 0; reading = 0;
}

The writer was transformed from a CPU-bound, syscall-heavy loop into a cache-friendly streaming pipeline.

// ❌ Old — O(N × T) comparisons
for (int i = 0; i < threads_count; i++) {
    if (current < min_value) { ... }
}

// ✅ New — O(N log T) with a min-heap
HeapNode min = heap_pop(&heap);
heap_push(&heap, next_value);

For 500M integers and 6 threads, this eliminates billions of redundant comparisons.

// ❌ Old — format parsing + internal locking on every integer
fprintf(fp, "%d\n", value);

// ✅ New — inline integer-to-ASCII, zero overhead
pos += fast_itoa(min.value, buffer + pos);

fast_itoa is a fully inlined custom converter with no format parsing, no type handling, no stdio overhead.

// Accumulate in user-space buffer, flush only when full
if (pos + 16 >= BUFFER_SIZE) {
    fwrite(buffer, 1, pos, pfile);
    pos = 0;
}
// Plus stdio-level buffer for double buffering
setvbuf(pfile, NULL, _IOFBF, BUFFER_SIZE);

Reduces write syscalls from millions to a handful.

This project requires a Linux system with the POSIX threads library (pthreads).

Clone the repository

git clone https://github.com/hitalloazevedo/mergesort
cd mergesort/v2

Compile

make

Run

./build/main -t <T> <F1> <F2> ... <FN> -o <output_file>

Example — run predefined test cases

./case1.sh   # -t 1  (1 thread)
./case2.sh   # -t 2  (2 threads)
./case3.sh   # -t 4  (4 threads)
./case4.sh   # -t 6  (6 threads)
./case5.sh   # -t 12 (12 threads)

Input files must be located inside /data. Extensions .dat or .txt are recommended.

Hitallo Alves Teles Azevedo

This project is licensed under the MIT License.