In this writeup, I assume that the name of the array to be sorted is A, that it is N entries long, that the entries are indexed 0 to (N - 1) [inclusive], that element number i of the array is referenced by A{i}, and that the array is to be sorted so for all integers i and j between 0 and (N - 1) incusive, (A{i} ≤ A{j}) iff (ij) [i.e. A{0} contains the lowest-valued element and the values of successive entries in A are nondecreasing].

The basic idea of the bubble sort is to apply the divide and conquer method; reduce the problem of sorting an entire array to the problem of sorting two adjacent elements, then apply this simpler problem in a way that will accomplish the larger problem. The problem of sorting an adjacent pair of elements is very simple; if the element at the lower index has a greater value then the pair needs to be swapped, otherwise the pair are already sorted [relative to each other, at least - not necessarily sorted in the larger context of the entire array]. A 'pass' is made through the array, sorting the pair A{0} and A{1}, then the pair A{1} and A{2}, and every pair, in order, up to A{N - 2} and A{N - 1} [thus, a pass consists of (N - 1) adjacent-pair-sorts]. It can be proved that after each pass, at least one more element is guaranteed to be in the correct position, so at most (N - 1) passes are necessary to sort the entire array [if (N - 1) elements are properly sorted, there's no place for the Nth element to be but it's properly sorted place too]. A simplistic implementation of the bubble sort looks like this:

``` i := 0 while (i < (N - 1))   j := 0   while (j < (N - 1))     if (A{j} > A{j + 1})       swap A{j} and A{j + 1}     end if     j := (j + 1)   end while   i := (i + 1) end while ```

This takes (N - 1)2 adjacent-pair-sorts. By realising that after one sweep, the greatest element must be at the highest index and generalising from there, one can see that the highest elements can be ignored on later passes so new, better code can be written:

``` i := (N - 1) while (i > 0)   j := 0   while (j < i)     if (A{j} > A{j + 1})       swap A{j} and A{j + 1}     end if     j := (j + 1)   end while   i := (i - 1) end while ```

This takes ((N - 1) * (N - 2) / 2) adjacent-pair-sorts, less than half the number of the first code. Another optimisation can be added: if, on any pass, there are no swaps, this means that the array is sorted, and the sort algorithm can end. This adds a little more processing to each pass, but the beneft of saving a few passes can so outweigh the cost of the little extra processing in each pass that it is generally considered a good idea to include it.

``` i := (N - 1) DidSwap := true while ((i > 0) ∧ (DidSwap = true))   DidSwap := false   j := 0   while (j < i)     if (A{j} > A{j + 1})       swap A{j} and A{j + 1}       DidSwap := true     end if     j := (j + 1)   end while   i := (i - 1) end while ```

Finally, when one considers a mostly-sorted array [e.g. an array that is fully sorted, but has an extra element added onto the end with a value lower than any other entry], another optimisation comes to mind. A pass through the array from the lowest index to the highest ensures that the greatest element is properly sorted. Likewise, a pass from the highest index to the lowest would ensure the least element is properly sorted. A sweeping back-and-forth of passes would therefore most likely perform better on a mostly-sorted array.

``` limit{-1} := -1 limit{1} := (N - 1) i := 0 direction := 1 DidSwap := true while (((limit{-1} + 1) < limit{1}) ∧ (DidSwap = true))   DidSwap := false   while (i ≠ limit{direction})     if (A{i} > A{i + 1})       swap A{i} and A{i + 1}       DidSwap := true     end if     i := (i + direction)   end while   limit{direction} := (limit{direction} - direction)   i := (limit{direction} - direction)   direction := -direction end while ```

All array entries with index lower than or equal to limit{-1} are sorted, and all array entries with index higher than limit{1} are sorted, at all times. direction is 1 for an ascending sweep through the array, and is -1 for a descending sweep. Once a pass is completed, the appropriate limit has direction subtracted from it, so the next pass in the same direction won't go unnecessarily far into a part of the array which is known to be sorted already. i is reinitialised to start the sweep in the opposite direction, so that it doesn't start in the part of the array which is known to be sorted already, and direction is inverted so the next sweep is in the opposite direction.