An O(n log₂n) hybrid sorting algorithm on 2-D grid

摘要

The authors have designed a hybrid sorting algorithm usingnheapsort and a modified version of quicksort. It consists of two phases:npreprocessing and sorting. In the preprocessing phase, input data arenrandomly placed on a square grid and sorted in column-wise ordernfollowed by row-wise order using heapsort. In the sorting phase, thenpreprocessed data are treated as a linear list and sorted by a modifiednquicksort. The sort time complexity of the hybrid method is O(nnlog₂n), and maintains a fairly constant value for a fixed nnfor any presortedness of the input data. The granularity of parallelismnin the hybidsort is large, and therefore it is suitable for parallelnprocessing