| Home | Sign up! | Projects | Seminars | Research Notes | Today's Lecture | About |

Update Research Note Form
 Course: Research Note Topic: Research Note Description: This algorithm was designed by E.K.Batcher
The first and only criteria for this sorting algorithm is that the number of elements must be of the order of 2n. Now the steps involved in doing so are:

i)Divide the list of elements into 2 halves and sort them using any efficient recursive sorting algorithm.

ii) Now swap the 2 halves.

iii) Now take the elements in the odd and even positions resp. and sort them into 2 lists.

iv) Now merge the 2 lists placing the elements of the odd positioned elements in the odd positions and resp. for the even positioned elements.

v) Now except the first and last elements, compare and exchange(if required) pairs of consequtive even-odd elements(specifically in that order).

Note: The Time complexity T(n) of this sorting algorithm is nlog(n).

SORTING NETWORKS:

Sorting networks are employed when we have to sort lists of some specific size. These are very simple devices that only do compare -exchange operations.
eg. consider the below illustrated 4-element sorting network.

c__.__ b ____ b__.__ a____a ____a
b__|__ c ____ c__|__ c__.__ c__.__b
d____ d__.__ a__|__ b__|__ b__|__c
a____ a__|__ d____  d__|__ d____ d

|___________| |____________| |_____|
step1             step2            step3

A further in-depth explaination will be provided in the course of the next few days. Your Password: