Algorithmics - The Computing Universe: A Journey through a Revolution - page 89

called bubble sort and merge sort . Suppose we have the following list of eight
names that we want to sort alphabetically:

Bob
Ted
Alice
Pat
Joe
Fred
May
Eve

Letters are usually represented in a computer using the so-called ASCII
scheme, an acronym for the American Standard Code for Information
Interchange. All of the twenty-six Standard English characters, plus punctua-
tion and other symbols can be represented as a seven-bit ASCII code. Hence we
can arrange for the computer to understand what we mean when we ask for
two numbers to be compared and placed in alphabetical order.
Let's first examine the bubble sort algorithm. It works by repeatedly com-
paring adjacent names and interchanging them if they are out of alphabetical
order. We start by considering the bottom two names on the list:

May Eve

swap

Eve May

Next we move the “bubble” up and consider the next pair on the list:

Fred Eve

swap

Eve Fred

We repeat the process until the bubble of paired names has reached the
top. We are then guaranteed that the correct first name is at the top of the list.
The detailed workings of this first iteration are shown in Figure 5.5 .
Now start again, with the bubble again at the bottom of the list. At the
end of this second pass through all of the names on the list, the second name
will be in the correct position, second from the top. For sorting all eight items
correctly we need to repeat this process seven times. You can see why this
algorithm is called the bubble sort, because the sorted names bubble up to
the top.
The bubble sort algorithm gets the job done, but it is not a very efficient
way to sort a large list. Sorting is such a common task that computer scientists
have spent a lot of time looking for efficient sorting algorithms. One very clever
and practical algorithm is called merge sort. It was invented by von Neumann