Using your Head is Permitted

One way to think about this is that the statement "Bubble sorting is an O(n²)-time operation" is simply false or, at best, a useful approximation. Another, perhaps more rewarding way to look at it is to recognize that computation complexity is a function of the computational model one works in, and that in most cases where we deal with complexity we implicitly consider a computational model where, unlike in the Turing-machine computational model, operations such as comparison of integers are atomic O(1)-time operations.

In mathematical riddles hidden assumptions are always problematic, for which reason I am describing here a complete computational model, composed entirely of operations that are almost invariably treated as atomic O(1)-time operations, which is the computational model this month's question refers to. The solution you are requested to provide is a description of an algorithm implementable in this model, which, when implemented in the model, will run in the desired complexity.

The model's operations are listed below. Where additional details are given in parentheses, they are meant to disambiguate the description. The operations supported by the model are:

Regarding integers

• The four basic arithmetic operations (addition, subtraction, multiplication and division) as well as modulo-taking are all O(1).
• The bitwise operations AND, OR and NOT are O(1). (We use the standard 2's-complement representation of integers for the bitwise operations, so "14 AND 13 = 12" and "14 AND -13 = 2".)
• Comparisons (less than, greater than, equals to) are all O(1).
• Shift-left and shift-right by n bits, for any integer n, are O(1). (The result of this is the same as multiplication/division by 2ⁿ.)

Regarding arrays

• Allocating/deallocating an array of any size is O(1)-time. (An array stores a single integer in each of its cells. Cell indices are integers. Arrays start off as non-initialized, meaning that if an array cell is read before it was ever written to, the value read may be any integer. Arrays can not change their sizes once allocated.)
• Accessing a given array position for either reading or writing is O(1). (Accessing an array position outside the array bounds [either by use of an index with a negative value or one larger than the array's maximum] leads to undefined results. Array indices are zero based.)
• Input and output of the program are special cases of array reading and array writing (respectively), and follow the same complexity. (Also: integer variables are special cases of arrays of size 1. Integer constants [i.e. program literals] are like variables, but they are, unlike regular arrays, initialized to their constant value and cannot be given new values.)

Regarding flow control

• Jumps are performed in O(1) time.
• Conditional jumps are perfomed in O(1) time, in addition to the time it takes to evaluate the condition.

As stated before, all of these operations are almost invariably assumed to be O(1), anyway, which makes this month's question all the more interesting. It is:

Design an algorithm for sorting n integers that takes O(n) time.

List of solvers: