[1]

0 and 1 is enough but not practical enough

1. What is Sorting?

Sorting, in mathematical sense, is nothing but process of arranging items in a sequence ordered by some criterion. In many cases, items are real numbers and criterion asks us to rearrange them in non decreasing order. For example, given sequence of 10 real numbers

(sorry if the numbers are confusing :] ) the correct sorted output of this sequence would be

In order to sort given sequences, we must perform repeated comparisons between two chosen numbers. These are called comparison sorting.

There are indeed sorting techniques which do not accompany comparisons between numbers, but these algorithms require further restrictions on the input, such as set of integers or evenly distributed over a closed interval something like that. Since we are dealing with inputs with no restrictions on the real line, we must use comparison sorts.

2. Modeling the Process of Sorting

Now, any comparison sorting can be represented using the following diagram.

In detail, it consists of three parts

1. Input sequence

2. Output sequence (which is rearrangement in non decreasing order)

3. A network that actually performs comparisons and rearrangements.

The important part is the network . How do we specify the structure of ? It should contain all the information about comparisons we've done. For simplicity, let's look at the simplest network, which rearranges two numbers.

The simplest network produces minimum and maximum of two numbers. This can be modeled as a controller which sends smaller number to the top, and the other one to the bottom. So we define the fundamental network, called comparator , as follows.

---

For input sequence and given integer , comparator is a function such that

So a comparator is just a network of comparing two numbers , leaving others unchanged. - [2]

---

Since sorting is just simultaneous application of comparators, an arbitrary sorting network is modeled as follows.

[3]

where each vertical line segements represent comparators. For example, in the following sorting network you can see that simultaneous application of 5 comparators gives sorted output <1,2,3,4>.

[4]

3. All Possible Inputs?

Suppose we are given a sorting network , without any information about itself. That is, we do not know the structure of ; position of each comparators as well as algorithm behind it. And here comes the question.

How do we know the correctness of ?

Since we do not know the structure, what we can do is just comparing input - output relationships produced by .

The total number of orderings such that length sequence can have is , so it is impossible to investigate every input-output relationships if gets large. Our real question is then,

Is there a smaller collection of input sequences enough to guarantee is correct ?

The answer is... YES! and this is called 0-1 sorting principle.

4. 0-1 Sorting principle

Now we state the 0-1 sorting principle. - [5]

---

0-1 Sorting Principle.
If a sorting network sorts every sequence of 0's and 1's (that is ) , then it sorts every other arbitrary sequence of length .

---

So only number of testing is enough. To prove this we need two ingredients. For any length sequence , we define

---

A non-decreasing function on domain and

Multi-valued function .

---

Using definition of comparator, we have

Using function diagram,

The meaning of this diagram is simple, that

is equal to

commutative . For an arbitrary sorting network (which is a composition of comparators) and a monotonic mapping we have therefore

Hardest Part -[5]

Now let be a sorting network such that sorts all sequence of 0's and 1's correctly, but there exists an input - output relationship which the output is not sorted. Then there is an integer such that

The clever trick is to construct a following non-decreasing function such that

Surely . So

is unsorted sequence. Using commutative relationship,

and since we assumed that sorts 0-1 sequence correctly, we get the contradiction because is by definition, a 0-1 sequence.

5. Application ? - Hmm...

So in the case of unknown sorting network (or algorithm), number of all 0-1 sequences give the answer for correctness. But is small enough to be tested? Well,

• It is definitely smaller than for , (in fact, )

• but itself is also exponential!

Try . If you want to test the correctness of algorithm that sorts length 30 sequence, you should investigate 1,073,741,824 in-out relationships, which exceeds 1 billion ...

Surely it is correct but not practical for real world applications... Also, the sad fact is that is actually tight bound for testing the correctness. Testing less than does not guarantee the correctness. (This is easy you can verify by yourself).

6. Conclusion

0-1 is enough but not practical enough.

7. Citations

[1] Image Source Link

[2] http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/sortieren.htm (definition citation)

[3] Image Source Link

[4] Image Source Link

[5] D.E. Knuth: The Art of Computer Programming, Vol. 3 - Sorting and Searching. Addison-Wesley (1973)