Consider the following representation of data in an array. It is not in any sorted order, and we wish to sort the data so that the higher values are to the left and the lower values are to the right. We use the convention that the leftmost array element is element zero, and the index increases by one as we move to the right.
The first step of the process is to compare the contents of element  with the contents of element . If element  is less than element  the two items are unsorted relative to each other, and they must be exchanged. In this case the two elements are already in order, and should not be exchanged.
Next, we compare element  with element . Again, if the two items are not sorted relative to each other they must be exchanged. In this instance, 6 > 2 so the two items must be exchanged. After performing the exchange, the array will look like this:
The third step requires that element  be compared with element . Again, if the two are out of order, the two items must be exchanged. In this example 7 > 2 so the exchange takes place, modifying the array to look like this:
The fourth step is to compare element  with element , In this example, 9 > 2 so the exchange takes place, leaving the array looking like this:
Notice that the lowest value in the array has been ‘bubbled’ to the rightmost element of the array. This signals the end of the first phase of the sort, as we have now reached the end of the array. (To compare element  with element  would take us off the end of the array – in some programming languages this would trigger a run-time error.)
Next: BS Pass 2