Index of /cag/raw/benchmark/suites/mergesort

	Name	Last modified	Size	Description
	Parent Directory		-
	build/	2009-05-14 17:36	-
	src/	2009-05-14 17:36	-

Merge Sort Benchmark

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.