Sorting Algorithms and Comparison Networks

Comparison Networks Sorting Sorting binary values Sorting arbitrary numbers Implementing symmetric functions

Sorting Algorithms Example Mergesort(array[1, ,n] of Integers): begin Mergesort(array[1, ,n/2]); Mergesort(array[n/2+1, ,n]); Merge(array[1, ,n/2], array[n/2+1, ,n]); end (m ) O comparisons required to merge two arrays of size m/2 ( log n ) O n comparisons to sort n elements Order of comparisons not fixed in advance. Not readily implementable in hardware.

Sorting Networks C D B A A B C D Sorting Network Order of comparisons fixed in advance. Readily implementable in hardware. number , ) (log depth n O 2 2 of comparison s ( log n ) O n

Sorting Networks (binary values) inputs outputs 1 0 0 1 0 0 1 1 0 0 0 0 1 1 1 1 Sorting Network sorted

Comparator (2-sorter) outputs inputs min(x, y) x C max(x, y) y

Comparator (2-sorter) outputs inputs min(x, y) x max(x, y) y

Comparison Network 1 0 0 0 0 1 0 0 width n 1 0 1 1 0 1 1 1 depth d

Comparison Network 1 0 0 0 0 1 0 0 n / 2 comparisons per stage 1 0 1 1 0 1 1 1 d stages

Sorting Network Any ideas?

Sorting Network inputs outputs Sorting Network ... ... ... n 1 n

Insertion Sort Network inputs outputs depth 2n 3

Batcher Sorting Network Next Lecture 2n depth (log ) O

Sorting Arbitrary Numbers outputs inputs min(x, y) x max(x, y) y x, y can be values from any linearly ordered set, e.g., integers, reals, etc.

Integer Comparator X, Y: integers represented as m-bit binary strings. Comparison function: 1 if X > Y, 0 otherwise. C(X,Y) = Idea: use C(X,Y) to select the min and the max of X and Y.

Sorting Arbitrary Numbers 2 2 2 9 9 6 6 2 sorted 6 9 9 6

Sorting Arbitrary Numbers 1 1 1 1 5 4 4 5 sorted 4 5 5 4

Sorting Arbitrary Numbers 3 3 3 3 7 0 0 7 not sorted 0 7 7 0 How can we verify if a network sorts all possible input sequences?

Sorting Arbitrary Numbers inputs outputs Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 0 000 000 0 0 0 0 0 0 0 0 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 0 000 001 000 001 0 0 0 0 1 1 1 1 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 0 000 001 010 000 001 001 1 0 0 1 0 1 1 0 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 0 000 001 010 011 000 001 001 011 1 1 1 1 1 1 1 1 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 1 000 001 010 011 100 000 001 001 011 001 1 0 0 0 0 1 1 0 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 1 000 001 010 011 100 101 000 001 001 011 001 011 1 1 1 0 1 1 1 1 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 1 1 1 1 000 001 010 011 100 101 110 000 001 001 011 001 011 101 1 0 0 1 0 1 1 0 Try all possible 0/1 sequences. not sorted!

Sorting Arbitrary Numbers inputs outputs 1 1 1 1 000 001 010 011 100 101 110 111 000 001 001 011 001 011 101 111 1 1 1 1 1 1 1 1 Try all possible 0/1 sequences. not sorted!

Sorting Arbitrary Numbers

Sorting Arbitrary Numbers inputs outputs Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 0 000 000 0 0 0 0 0 0 0 0 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 0 000 001 000 001 0 0 0 0 1 1 1 1 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 0 000 001 010 000 001 001 1 1 0 1 0 0 1 0 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 0 000 001 010 011 000 001 001 011 1 1 1 1 1 1 1 1 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 1 000 001 010 011 100 000 001 001 011 001 1 1 0 0 0 0 1 0 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 0 0 0 1 000 001 010 011 100 101 000 001 001 011 001 011 1 1 1 0 1 1 1 1 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 1 0 0 1 000 001 010 011 100 101 110 000 001 001 011 001 011 011 1 1 1 1 0 1 1 0 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 1 1 1 1 000 001 010 011 100 101 110 111 000 001 001 011 001 011 011 111 1 1 1 1 1 1 1 1 Try all possible 0/1 sequences.

Sorting Arbitrary Numbers inputs outputs 000 001 010 011 100 101 110 111 000 001 001 011 001 011 011 111 all sorted! Try all possible 0/1 sequences.

Zero-One Principle If a comparison network sorts all possible sequences of 0 s and 1 s correctly, then it sorts all sequences of arbitrary numbers correctly.

Lemma Given For a monotonically increasing function f, 0 a 0b 1a 1b

Lemma Given For a monotonically increasing function f, ( ) (0b ) 0 a 0b f 0 a f ( ) (1b ) 1a 1b f 1a f

Proof: Lemma min( , ) 0 a 0a a 1 max( , ) 0a a 1a 1

Proof: Lemma ( ) min( ( ), ( )) f 0 a f a f a 0 1 max( ( ), ( )) f a f a ( ) f 1a 0 1

Proof: Lemma f is monotonically increasing: y x ( x f ) ( ) f y ( ) min( ( ), ( )) f 0 a f a f a 0 1 max( ( ), ( )) f a f a ( ) f 1a 0 1

Proof: Lemma f is monotonically increasing: y x ( x f ) ( ) f y (min( , )) f 0a a ( ) f 0 a 1 (max( , )) f 0a a ( ) f 1a 1

Proof: Lemma f is monotonically increasing: y x ( x f ) ( ) f y (0b ) f ( ) f 0 a (1b ) ( ) f f 1a

Generalization Given 0b 0c 0 a 0 d 1b 1c 1a 1 d 2b 2c 2 a 2 d

Generalization For a monotonically increasing function f, (0b ) (0c ) f f ( ) ( ) f 0 a f 0 d (1b ) (1c ) f f ( ) ( ) f 1a f 1 d (2 b ) (2c ) f f ( ) ( ) f 2 a f 2 d (by induction)

Proof: Zero-One Principle Suppose a) the network sorts all sequences of 0 s and 1 s, b) there exists a sequence that it doesn t sort, i.e., 1 0 , a a a , such that j i a a but is placed before in the output. ,..., n a 1 ia j a j ia Define x 0 if 1 otherwise ia f (x) =

Proof: Zero-One Principle 0 a 1a 0 a 1a ... ... Sorting Network j a ia ... n a n a 1 1

Proof: Zero-One Principle ( ( ) ) ( ( ) ) f f 0 a 1a f f 0 a 1a ... ... Sorting Network ( ( ) ) f f j a ia ... ( ) f n a n a ( ) f 1 1