This document describes the structure and execution of Merge Sort, implemented as mergeSort function.
The algorithm works in software as follows:
1.Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted).
2.Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
For FPGA implementation, a hardware oriented design is realized in the Merge Sort primitive.
The Merge Sort primitive has an internal comparator to sort two input stream into one output stream.
Steps for descending (vise versa):
1.Read the 1st right value and the 1st left value.
2.Compare the two value and output the larger one.
3.If the output value in step2 is from the right stream and the right stream is not empty, then keep read value form the right stream. Otherwise, read from the left stream.
4.If both stream are empty, break the loop. Otherwise, return to step2.