Sorting and searching

a₁ assume asymptotic average number B-tree b₁ balanced trees binary search binary tree blocks bubble sort buffers CACM Compare consider construction contains corresponding defined deletion digital search tree disk distribution elements empty equal example exercise external nodes external path length Fibonacci Fibonacci tree formula given hash function heapsort hence initial runs input integers internal internal sorting JACM K₁ keys linear probing LINK LLINK Math memory merge pattern minimum multiset number of comparisons number of inversions number of probes obtained operations optimum output P₁ pass phase possible priority queue probability problem Program Prove quicksort R₁ radix sort random records replacement selection rewind RLINK search tree Section sequence shows sorting algorithm sorting network step straight insertion subfile subtree successful search tableau tape Theorem total number