Arranging Data Too Large to Fit in Main Memory, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 17.10 Free with a free account

Arranging Data Too Large to Fit in Main Memory

Data Structures and Algorithms · Chapter 17: Graphs and MemorySection 17.10 · lesson 87 of 878 min · free with a free account

← Navigating Massive Disk Datasets with Multi-Level Index Trees

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

External merge sort, replacement selection, and choosing fan-in and block size.

  • Count the block transfers of an external merge sort
  • Compute the number of merge passes from the number of runs and the fan-in
  • Trace replacement selection and explain why it produces longer runs
  • Choose a fan-in and block size that balance seeks against passes

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,097 words). Read along, or search it.

Opening Question

Sorting a File You Cannot Load

Memory holds 10,000 records. The file holds a million, a hundred times more. Sort it. The data lives on a disk, which is thousands of times slower than memory, and hands over data in blocks, not one value at a time. So what's the cheapest way to sort a file you can't even load?

Cost Model

Block Transfers and Two Phases

Call the file N records, memory M records, and a block B records. The cost is the number of block transfers: each block read from disk, or written to it. On a spinning disk, every transfer pays a seek of several milliseconds. At 8 milliseconds, that's 8 million nanoseconds: the time of millions of comparisons in memory. That points to merge sort. Merging reads each input from start to end, and writes its output the same way, exactly what a disk does well. So external merge sort has two phases. Run formation cuts the file into sorted runs, as long as memory allows. Then merging combines k runs at a time, until one run is left.

Run Formation

Load, Sort, and Write Sorted Runs

This program counts every block it moves. The disk is simulated with arrays, but the counting follows the same rule: one transfer per block. Run formation is the simplest step. Load M records, sort them with any in-memory sort, and write them out as one run. Repeat until the input ends. Run it on a million records, with memory for 10,000 and blocks of 1,000. That's 100 runs, and each of the 1,000 blocks is read once and written once.

Multiway Merge

Merging Nine Runs at a Time

Merging two runs means comparing their front values and writing the smaller. A k-way merge does the same with k runs at once, using a heap of their front values. Take the smallest, write it, and refill the heap from that same run. Memory holds one block from each input run, plus one output block. So the fan-in is limited to M over B, minus one. Here that's 10 blocks of memory, so 9 runs at a time. The passes cut 100 runs to 12, then 2, then 1. Three merge passes, 8,000 transfers in all, and the output is sorted correctly.

Formula

Predicting the Transfer Count

That count can be written down in advance. Run formation reads and writes every block once. So does each merge pass. With fan-in k, each pass divides the number of runs by k. So the passes needed are the smallest p with k to the p at least R, the number of runs. Here, 9 squared is 81, less than 100, so p is 3. The total is 2 times N over B, times 1 plus p: 2 times 1,000, times 4. Exactly 8,000.

Quick Check

Merge Passes for Two Hundred Runs

Quick check. A sort forms 200 runs, and memory allows a fan-in of 6. How many merge passes does it need? Pause and predict. Three. Six squared is only 36 runs' worth, short of 200. Six cubed is 216, which covers them. Thirty-four would be 200 divided by 6: that's the number of runs after the first pass, not the number of passes.

Replacement Selection

Runs Longer Than Memory

Fewer runs can mean fewer passes. Replacement selection makes runs longer than memory, using a min-heap of M records. Repeatedly, remove the smallest record, write it to the current run, and read the next input record. If it's at least as large as the last one written, it joins this run. If it's smaller, it's tagged for the next run, and waits in the heap behind everything in the current one. Run it on fourteen values with room for only three. The runs come out with lengths 4, 6, and 4: longer than memory, because large enough records pass straight through.

Measurement

Fifty-One Runs Instead of a Hundred

How much longer, in practice? This program forms runs from a million records, with memory for 10,000. Load-sort-write always makes 100 runs. On random input, replacement selection made 51: runs about twice as long as memory, as a classic snowplow argument predicts. Ascending input becomes a single run, with no merging at all. Descending input gains nothing: every record waits for the next run. In our sort, 51 runs with a fan-in of 9 need only two passes. That's about 6,000 transfers instead of 8,000, a quarter fewer.

Quick Check

The First Run With Room for Two

Quick check. Replacement selection, with room for just two records, reads 5, 3, 8, 1, 9, 2, and 7. What is the first run? Pause and predict. Three, five, eight, nine. Three goes out first, and 8 is large enough to join. Then 5 goes out, but 1 is too small, so it waits. Eight goes out, and 9 joins. Nine goes out, and 2 waits too. The first run is twice as long as memory, and the second is 1, 2, 7.

Fan-In

Where the Pass Count Goes Flat

How much does the fan-in matter? This run sorts the million records as 100 runs, with blocks of 100 records, so any fan-in up to 99 fits. A binary merge needs 7 passes and 160,000 transfers. A fan-in of 16 needs only 2 passes: 60,000 transfers, about 2.7 times less. Then the curve goes flat. Sixteen squared is already 256, more than 100 runs, so fan-ins of 32 or 99 still need 2 passes. Memory spent on a bigger fan-in beyond that threshold buys nothing.

Block Size

Balancing Seeks Against Passes

Block size pulls two ways. Bigger blocks mean fewer transfers, but a smaller fan-in, which can add passes. This program models a disk: every transfer pays an 8 millisecond seek, then moves its block at 100 megabytes per second, with 100-byte records. It's a model, not a measured disk. Blocks of 100 need just 2 passes, but 60,000 seeks: 486 modeled seconds. Blocks of 2,000 need 4 passes, yet only 5,000 transfers: 50 seconds. At 2,500, the fan-in drops to 3, five passes are needed, and the time creeps back up. The best block size sits in the middle.

Decision Guide

Spending Memory Wisely

So the choices come down to memory. Use all of it to form runs, and prefer replacement selection when the input is random, or partly in order. Make the fan-in just large enough to reach the pass count you need, and always keep one block for output. Spend leftover memory on larger blocks, and test candidate block sizes with the formula. Count passes first: every pass costs two transfers per block of the file.

Key Takeaways

External Sorting in Brief

To sum up. When data won't fit in memory, cost is counted in block transfers. External merge sort forms sorted runs, then merges k at a time, with k equal to M over B, minus one. The total is two times N over B, times one plus the number of passes. Replacement selection doubles run length on random input, and the best block size balances seeks against passes.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Arranging Data Too Large to Fit in Main Memory

How does external merge sort work?
External merge sort handles data too large for memory in two phases. Run formation loads as many records as memory holds, sorts them, and writes each batch out as a sorted run. Merging then combines k runs at a time with a heap of their front values, keeping one block from each input run plus one output block in memory, until a single sorted run remains. Its cost is counted in block transfers.
How many passes does an external merge sort need?
The number of merge passes is the smallest p for which k to the power p is at least R, where k is the fan-in and R the number of runs. With 100 runs and a fan-in of 9, 9 squared is only 81, so three passes are needed. The total cost is 2 times N/B times (1 + p) block transfers, since run formation also reads and writes every block once.
What is replacement selection in external sorting?
Replacement selection forms sorted runs longer than memory using a min-heap. It repeatedly writes the smallest record to the current run and reads the next input record; a record at least as large as the last one written joins the current run, while a smaller one waits for the next run. On random input, runs average about twice the memory size, and ascending input becomes a single run.
How does block size affect external sorting?
Bigger blocks mean fewer transfers, and so fewer costly seeks, but they shrink the fan-in, which is M/B minus 1, and can add merge passes. In one disk model with an 8-millisecond seek, blocks of 100 records took about 486 seconds and blocks of 2,000 about 50, but at 2,500 the fan-in dropped to 3 and the time rose again. The best block size sits in the middle.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →