Advanced Programming I Lecture Notes

9 February 2006 • External Sorting


Outline

Massive Sorting

External Sorting

Is Sorting Necessary?

External Devices

Objectives

General Approach.

General Approach..

Basic Idea

Basic Idea Illustrated

Implementation Details

Balanced n-way Sort Merge

Analysis

The Initial Distribution

Exploiting Initial Order

Replacement Selection

Balance Problems

Unbalancing The Sort

Improved Unbalancing

Polyphase Merge Illustrated

Properties

Nonuniform Block Distribution

Analysis

References


This page last modified on 6 April 2006.

This work is covered by a
Creative Commons License.