| | | | | | 9.1 Example: Sorting a List of Uniformly Distributed Integers | | | | | | | | | We have chosen to investigate sorting to illustrate some of these processes. Sorting is a multi-faceted problem. It is fundamental to many basic problems in computer science and engineering. According to Knuth,4 program was the first major "software" routine ever developed for automatic programming. Today, sorting, and its closely related cousin, searching, are perhaps most widely used in database servers. | | | | | | | | | There is no single "best" sorting algorithm on sequential computer hardware, and if anything, the situation is even more complicated in parallel. Issues that affect the choice of a sorting algorithm include: | | | |  | | | | | the size of the elements to be sorted; | | | | | | | | | the form of the desired result, e.g, is a permutation sufficient, or must the data actually be rearranged; | | | | | | | | | does each element have a corresponding, known integer key, or is the order implied solely by a comparison function; | | | | | | | | | the cost of comparing two objects relative to other operations (exchanging elements, interprocessor communication, pointer dereference, etc.); | | | | | | | | | availability of auxiliary primary storage, i.e., must the algorithm work "inplace," or may it allocate temporary storage; | | | | | | | | | limitations on primary storage and availability and characteristics of secondary storage, i.e., out-of-core or tape-based sorts; | | | | | | | | | the distribution of keys; | | | | | | | | | non-random structure in the input data, i.e., is the input data likely to be pre-sorted or almost pre-sorted; | | | | | | | | | the relative importance of worst-case vs. average-case behavior; | | | | | | | | | stability - the property that the ordering of elements that compare equal is preserved from the input to the output.' | | | | | | | | | While these considerations make it difficult or impossible to devise a universally optimal sorting algorithm, they also allow for constant refinements tailored to changing hardware, usage patterns, and the demands of specific applications. Sorting is also an example of an irregular, non-grid-based problem. As such, it illustrates techniques and algorithms rather different from those in Chapter 8. While it is widely believed that large, regular, numerical applications run well on Beowulf systems, good performance of irregular, non-numerical algorithms is less | | | | | | | | | | 4D. E. Knuth, The Art of Computer Programming volume 3: Sorting and Searching Addison Wesley, 1973, [pg 386] | | | | |
