Directory Contents
The hardware structure that implements the merge sort is a binary tree
with the leaves of the tree each containing a single element of the
data set that is to be sorted. Each node of the tree performs a
comparison of its two inputs from its subnodes, stores the higher value
in a register which is connected to the output of the node, and then
tells the subnode that had the higher value to load a new value into
its register. The subnode that gets the load signal performs the same
operation, and so on, until a leaf node is hit. Once a leaf node gets a
load signal, it loads its register with a zero. As data is pulled off
the top of the tree, larger data values float to the top. The sort is
completed in O(N) time.