Columnsort

Columnsort is a family of sorting techniques that operate on data arranged in a rectangular grid and perform most work along the columns. It is used when data exceed available memory or when parallel hardware can exploit column-wise operations. In the typical form, elements are placed into a matrix with a fixed number of columns. Each pass sorts the elements in every column, then the data are redistributed (often by transposing or permuting columns to rows) so the next pass can sort along the other dimension. Repeated passes move the data toward a total order by the key.

Variants include column-sort networks, which realize the idea as a network of comparators operating on column data in parallel, and practical column-sorting procedures used in external or parallel sorting to manage I/O and memory. In a network, data are routed and compared across columns according to a fixed schedule, enabling sorting on hardware such as GPUs or multicore systems.

Algorithmic notes and complexity: Performance depends on the number of columns and rows, the stability of local sorts, and the redistribution step. In ideal models, a fixed number of passes yields a full sort; in external sorting the I/O cost dominates. Columnsort can minimize disk traffic by keeping active blocks in fast memory during passes while streaming others.

See also: Sorting network, External sorting, Matrix sort.