Sorting Algorithms
Béla Bollobás · Cambridge University Press eBooks · 2001
Random graph techniques are very useful in several areas of computer science. In this book we do not intend to present a great variety of such applications, but we shall study a small group of problems that can be tackled by random graph methods. Suppose we are given n objects in a linear order unknown to us. Our task is to determine this linear order by as few probes as possible, i.e. by asking as few questions as possible. Each probe or question is a binary comparison: which of two given elements a and b is greater? Since there are n ! possible orders and k questions result in 2 k different sequences of answers, log 2 ( n !) = {1 + o (1)} n log 2 n questions may be needed to determine the order completely. It is only a little less obvious that with {1 + o (1)} n log 2 n questions we can indeed determine the order. However, if we wish to use only {1 + o (1)} n log 2 n questions, then our later questions have to depend on the answers to the earlier questions. In other words, our questions have to be asked in many rounds , and in each round they have to be chosen according to the answers obtained in the previous rounds. For a sorting algorithm, define the width as the maximum number of probes we perform in any one round and the depth as the maximal number of rounds needed by the algorithm.