External Sort Engine

A pure C implementation of external merge sort for sorting datasets that are too large to fit entirely in main memory.

Overview

Traditional in-memory sorting assumes that the complete dataset can be loaded into RAM. External sorting solves a different problem: sorting data when the input is larger than the available memory.

ExternalSortEngine uses disk-backed intermediate data and merges sorted runs to produce the final ordered result.

Features

• External merge sort
• Disk-based sorting
• Configurable memory usage
• K-way merge
• Min-heap based merge management
• Pure C implementation
• Separate source, header, and test directories

High-Level Algorithm

Input file
    │
    ▼
Read a bounded chunk
    │
    ▼
Sort chunk in memory
    │
    ▼
Write sorted run to disk
    │
    ├── repeat
    │
    ▼
K-way merge
    │
    ▼
Sorted output

This approach limits memory consumption while allowing datasets larger than available RAM to be processed.

Complexity

For N records and M records that can be processed in memory, external merge sort typically performs work proportional to:

O(N log(N/M))

with additional I/O costs from writing and reading intermediate runs.

The K-way merge uses a min-heap, giving approximately O(log K) work per emitted record for the merge structure.

Project Structure

ExternalSortEngine/
├── includes/
├── sources/
├── tests/
├── LICENSE
└── README.md

Building

The project is written in C. A typical compiler invocation is:

cc -Iincludes sources/*.c -o external_sort

Adjust the command to match the source layout and compiler available on your system.

Testing

The repository contains a tests/ directory for validating sorting and merge behavior.

Important cases include:

• Small input files
• Input larger than the configured memory budget
• Duplicate values
• Already sorted input
• Reverse-sorted input
• Empty input
• Multiple intermediate runs

Why This Project?

This project focuses on a practical systems problem: how to process data when memory is the limiting resource.

It demonstrates:

• External algorithms
• File I/O
• Memory constraints
• Heap-based merging
• Algorithmic trade-offs between CPU, RAM, and disk

License

MIT License.