Odd–even sort

Key takeaways

Odd–even sort belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Odd–even sort to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Odd–even sort from memory before moving on to harder problems.

Reference excerpt

In computing, an odd–even sort or odd–even transposition sort (also known as brick sort or parity sort) is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a comparison sort related to bubble sort, with which it shares many characteristics. It functions by comparing all odd/even indexed pairs of adjacent elements in the list and swapping pairs where in the wrong order (where the first is larger than the second). The next step repeats this for even/odd indexed pairs (of adjacent elements). Then it alternates between odd/even and even/odd steps until the list is sorted.

Sorting on processor arrays On parallel processors, with one value per processor and only local left–right neighbor connections, the processors all concurrently do a compare–exchange operation with their neighbors, alternating between odd–even and even–odd pairings. This algorithm was originally presented, and shown to be efficient on such processors, by Habermann in 1972. The algorithm extends efficiently to the case of multiple items per processor. In the Baudet–Stevenson odd–even merge-splitting algorithm, each processor sorts its own sublist at each step, using any efficient sort algorithm, and then performs a merge splitting, or transposition–merge, operation with its neighbor, with neighbor pairing alternating between odd–even and even–odd on each step.

Batcher's odd–even mergesort A related but more efficient sort algorithm is the Batcher odd–even mergesort, using compare–exchange operations and perfect-shuffle operations. Batcher's method is efficient on parallel processors with long-range connections.

Algorithm The single-processor algorithm, like bubblesort, is simple but not very efficient. Here a zero-based index is assumed:

Proof of correctness Claim: Let a 1 , . . . , a n {\displaystyle a_{1},...,a_{n}} be a sequence of data ordered by <. The odd–even sort algorithm correctly sorts this data in n {\displaystyle n} passes. (A pass here is defined to be a full sequence of odd–even, or even–odd comparisons. The passes occur in order pass 1: odd–even, pass 2: even–odd, etc.) Proof: This proof is based loosely on one by Thomas Worsch. Since the sorting algorithm only involves comparison-swap operations and is oblivious (the order of comparison-swap operations does not depend on the data), by Knuth's 0–1 sorting principle, it suffices to check correctness when each a i {\displaystyle a_{i}} is either 0 or 1. Assume that there are e {\displaystyle e} 1s. Observe that the rightmost 1 can be either in an even or odd position, so it might not be moved by the first odd–even pass. But after the first odd–even pass, the rightmost 1 will be in an even position. It follows that it will be moved to the right by all remaining passes. Since the rightmost one starts in position greater than or equal to e {\displaystyle e} , it must be moved at most n − e {\displaystyle n-e} steps. It follows that it takes at most n − e + 1 {\displaystyle n-e+1} passes to move the rightmost 1 to its correct position. Now, consider the second rightmost 1. After two passes, the 1 to its right will have moved right by at least one step. It follows that, for all remaining passes, we can view the second rightmost 1 as the rightmost 1. The second rightmost 1 starts in position at least e − 1 {\displaystyle e-1} and must be moved to position at most n − 1 {\displaystyle n-1} , so it must be moved at most ( n − 1 ) − ( e − 1 ) = n − e {\displaystyle (n-1)-(e-1)=n-e} steps. After at most 2 passes, the rightmost 1 will have already moved, so the entry to the right of the second rightmost 1 will be 0. Hence, for all passes after the first two, the second rightmost 1 will move to the right. It thus takes at most n − e + 2 {\displaystyle n-e+2} passes to move the second rightmost 1 to its correct position. Continuing in this manner, by induction it can be shown that the i {\displaystyle i} -th rightmost 1 is moved to its correct position in at most n − e + i {\displaystyle n-e+i} passes. Since i ≤ e {\displaystyle i\leq e} , it follows that the i {\displaystyle i} -th rightmost 1 is moved to its correct position in at most n − e + e = n {\displaystyle n-e+e=n} passes. The list is thus correctly sorted in n {\displaystyle n} passes. QED. We remark that each pass takes O ( n ) {\displaystyle O(n)} steps, so this algorithm has O ( n 2 ) {\displaystyle O(n^{2})} complexity.

References

Illustrations

Worked examples

Example 1 — a first encounter with Odd–even sort

Start with the simplest possible case. Write down what Odd–even sort claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Odd–even sort before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Odd–even sort ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Odd–even sort

In research: Odd–even sort appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Odd–even sort in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Odd–even sort is common in secondary-school and first-year university syllabi. It links to neighbouring topics Comparison sorts, Stable sorts, so understanding it makes those chapters shorter.
In everyday life: Look for Odd–even sort outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Odd–even sort in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Odd–even sort means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Odd–even sort out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Odd–even sort in simple terms?

In computing, an odd–even sort or odd–even transposition sort (also known as brick sort or parity sort) is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a comparison sort related to bubble sort, with which it shares man…

Why does Odd–even sort matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Odd–even sort?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Odd–even sort.