Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Stable sort — where it appears

A sort that keeps equal keys in the order they arrived. It is what lets a merge of runs be correct without comparing positions, since a merge that takes from the left run on a tie preserves the order, and it is the property an in-place merge has to pay for when its buffer is short.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

125102050100buffer, as a share of the filemoves a key of the file (log scale)1/41/161/641/2561/10241/4096pieces by insertionpieces by mergingmerge sort, whole tail65,536 keys, a late tenth from the top fifthmoves counted, sorted checked

Pieces that fit the buffer

A sorted file with a late tenth appended costs the buffer-limited stable merge sort 2.93 moves a key at a buffer of a 64th, fifteen times the least any sort could move, and two thirds of it is the tail sorting itself. Taking the tail a buffer at a time, inserting each key into a sorted piece in the buffer and merging the piece into the head, was predicted to bring that under two moves a key at small buffers. It never comes within twice the merge sort: insertion costs a quarter of a piece a key, and the smaller the pieces the more often each one's merge crosses the head's top fifth. The same pieces sorted in place by merging do pay, at 2.41 moves a key, and for a reason the proposal did not name: a piece that fits the buffer merges into the head without a single rotation. The gain lasts only while the tail belongs near the top of the file.

practice · Practice 1248163264buffer, as a share of the filemoves a key of the file (log scale)1/161/321/641/1281/2561/10241/4096pieces straight into the headthe proposed rulepieces merged to one firstmerge sort, whole file65,536 keys, a late tenth from the top fifthmoves counted, sorted checked

How many pieces the head can afford

A sorted file of 65,536 keys with a late tenth appended in random order can be sorted by taking the tail a buffer at a time, sorting each piece, and merging each into the head. It beats the buffered merge sort at a 64th of the file and loses at smaller buffers, because every piece's merge crosses the head's top keys again. Merging the pieces with each other first, while a round costs less than the crossings it removes, was predicted to win at every buffer. It wins at none. The first round always costs more than no rounds — 18.97 moves a key against 16.04 at a 1,024th — because a group larger than the buffer crosses the head by rotation, and the cost falls under the merge sort's only when the rounds run all the way, which is the merge sort. The head can afford thirteen pieces and not twenty-six; beyond that the best a tail can do is be one run.

practice · Practice

Named alongside it

The objects these essays reach for when they reach for this one.

Auxiliary spaceData movementMerge sortPredictionRotationBinary searchHonest limitInsertion sort

All concepts