CODEWITHSUNDEEP
algorithmsortingsorting-network
venkysmarty
venkysmarty

Reputation: 11431

butterfly network in sorting

I am studying even odd merge sort in Robert Sedwick Algorithms in C++.

As part of the text author mentioned about how odd-even merge sort can be used to implement parallel sorting in sorting network. In this context author mentioned butterfly network

My question is what is basically butterfly network and why is it called butterfly. Explanation with simple example will be appreciated.

I have googled it but not find simple explanation with example.

Upvotes: 1

Views: 2852

Answers (1)

mvw
mvw

Reputation: 5105

A butterfly network is a certain kind of sorting network. A sorting network can be viewed as an abstract network (e.g. a data flow network) or quite concrete as an electric circuit.

Those networks consist of input and output wires, and a couple of comparator multiplexers which route incoming values from one wire to another wire. It is an example of parallel sorting.

Butterfly Network

Source: Universität Leipzig

In the above diagramm, the inputs are on the left set, the ouputs are on the right side, the square boxes are comparators. The idea is that you can put arbitrary values from 0 to 15 at each input and they get routed to the ouputs by the comparators (which inspect the incoming value and decide to route to another wire or keep it on the same wire), all 0 values will be routed to the top output (000), all 1 values to the second output (001) etc.

The name is IMHO derived from the butterfly graph, which shows up for example in the Fast Fourier Transform, this kind of data flow with it's crossing ressembles a butterfly.

Butterfly Graph

Source: Wikipedia

If you look at the first diagram of the the butterfly network, you see it repeated over and over again.

Upvotes: 3

Related Questions