Principle - 2024.2 English

This document describes the structure and execution of Merge Sort, implemented as a mergeSort function.

The algorithm works in software as follows:

1. Divide the unsorted list into N sublists with each containing one element (a list of one element is considered sorted).
2. Repeatedly merge the sublists to produce new sorted sublists until there is only one 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 (vice versa):

1. Read the first right value and the first left value.
2. Compare the two values and output the larger one.
3. If the output value in step 2 is from the right stream and the right stream is not empty, then keep the read value from the right stream. Otherwise, read from the left stream.
4. If both stream are empty, break the loop. Otherwise, return to step 2.