The Movement Complexity of SortingResearch Paper
The comparison model counts comparisons and gives sorting its classical . On many machines that is not the whole cost: before two keys can be compared they must be brought within reach of the machine's read heads, and the heads travel. Head travel is already known to dominate in sequential models — on a Turing machine with one worktape and a…