The Art of Concurrency

Chapter 8. Sorting

This chapter examines the operation of concurrent sorting. At times, sorting has been estimated to account for over 80% of all processing cycles. Presenting the results from database queries, compiling a list of business investments with associated risk-reward measures, and figuring the company payroll are all operations that require sorting. Even with the large amounts of processing time spent on graphical interfaces, visualization processing, and video games, sorting remains a vital part of computation. Every time you get a list of URLs from a search engine, the results have been sorted, typically by some measure of relevance to your original query.

In this chapter I will first consider compare-exchange sorts. These are sorting algorithms that use the results from comparing two keys to determine the relative order of the elements with those keys. Movement of data items will be based on those results and will be the exchange of the positions of the two items under consideration. The final algorithm considered is radix sort, which compares bits within keys to determine movement of data. Example codes presented in this chapter will use arrays of integers, but you can apply these techniques to structures with a key field to distinguish between elements.

Bubblesort

Bubblesort was the first sorting algorithm I ever learned. It is easy to code and simple to understand. ...