Single-stage hardware sorting blocks and associated multiway merge sorting networks

A method for constructing a hardware multiway merge sorting network to merge 3 or more sorted input lists of values into a single sorted output list, using a sequence “q” of merge sorting stages, the method comprising steps of:

• combining Ncols sorted input lists, with Ncols>=3, each with a list length Nrowsq, into a rectangular structure, by setting each input list as a column in the rectangular structure, which then has a Ncols number of columns and a Nrowsq number of rows,
• defining several stages of sorting operations performed on the rectangular structure, so that the values in the rectangle are fully sorted after the merge sequence last stage,
• wherein each stage has both input and output signal connections defined in Ncols x Nrowsq 2-d arrays,
• wherein in each stage, the stage sorting operations are performed by single-stage hardware N-sorters, with Ncols>=N>=2, in which the outputs of each N-sorter are connected to the stage output 2-d array using the same 2-d coordinates which connect the stage input signal array to the N-sorter inputs, and
• stage input array signals which are not connected to an N-sorter input are passed through directly to the stage output 2-d array location matching the input 2-d array location.