Bitonic Sort (simulation)

* Bitonic sort consists ofO(n·log(n)²) comparisons inO(log(n)²) stages.

Figure 7:  Sorting network BitonicSort for n = 8

In order to form a sorted sequence of lengthnfrom two sorted sequences of lengthn/2, there are log(n) comparator stages required (e.g. the 3 = log(8) comparator stages to form sequenceifromdandd'). The number of comparator stagesT(n) of the entire sorting network is given by:
	T(n)  =  log(n) + T(n/2)
The solution of this recurrence equation is
	T(n)  =  log(n) + log(n)-1 + log(n)-2 + ... + 1  =  log(n) · (log(n)+1) / 2
Each stage of the sorting network consists ofn/2 comparators. On the whole, these areO(n·log(n)2) comparators.

 

** Simulation

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm