Types of Sorting

DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).

Types of Sorting: internal vs external

The first decision every sorting algorithm design has to make.

Internal sorting works entirely within main memory (RAM) — fine as long as the whole dataset fits. External sorting is needed when data is too large for RAM and must be sorted while mostly living on disk, using clever strategies to minimize slow disk reads/writes.

💡 One-liner: "When would you need external sorting instead of internal sorting?" → When the dataset is too large to fit entirely in RAM — e.g. sorting a multi-terabyte log file.

Why the distinction still matters

It looks like a historical footnote — memory is cheap now — but the boundary has simply moved rather than disappeared. The real question is never "does it fit in RAM" in the abstract; it is which storage level holds the data, and each level down is orders of magnitude slower.

Internal sorting optimises for comparisons. External sorting optimises for something else entirely: the number of passes over the data. An algorithm that makes fewer comparisons but reads the file three times loses badly to one that compares more but reads once, because a disk read costs thousands of times what a comparison costs.

💾 How external sorting actually works

SplitRead as much as fits in memory, sort that chunk internally, write it back as a sorted "run".

MergeMerge the runs together, reading only a small buffer from each at a time.

Why mergeMerging needs only the FRONT of each run in memory, so it never requires the whole dataset at once — the one property that makes it work on data larger than RAM.

💡 That last point is the exam answer worth having: merge sort is the basis of external sorting because merging is sequential — it reads each run front to back and never needs random access to the whole file. Quicksort, which jumps around the array, has no such property.

Syllabus points

Internal vs external sorting

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.