Insert sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insert sort provides several advantages:
1.Simple implementation;
2.Efficient for (quite) small data sets, much like other quadratic sorting algorithms;
3.The time complexity is O(nk) when each element in the input is no more than k places away from its sorted position;
4.Only requires a constant amount O(1) of additional memory space;
5.Sort a list as it receives it.
For its FPGA implementation, a dedicated structure is designed as follow:
The Insert Sort primitive has an internal shift register array to sort the input stream. It takes five steps to finish the sort processing of a stream with limited max sort number.
1.Build a group of shift registers, and the number of shift register is the maximum sort number;
2.Broadcasting the input value to every shift registers, then comparing size between the internal value of each shift register and the input value. For descending sort, run step3. Otherwise, run step4;
3.For descending sort, we should build a internal ascending array. If the input value is larger than array[i], then right shift array[i]. If the input value is less than array[i] and larger than array[i+1], insert input value to array[i+1];
4.For ascending sort, we should build a internal descending array. If the input value is less than array[i], then right shift array[i]. If the input value is larger than array[i] and less than array[i+1], insert input value to array[i+1];
5.If input stream is not empty, output the last value of the array and then return to step2. Otherwise, right shift the whole register array and output the last array value until the array is empty.