Sorting Data Arrange in Multidimensional Space


This analysis looks at the time operational complexity when sorting a set of data values arrange in a 2-dimensional (2-D) grid. The analysis seeks to identify and exploit potential techniques for speedup on sorting in general and for implementation on parallel systems. Results from the analysis are also generalised to develop parallel sorting systems for data arranged in m-dimensional space, where m is an integer > 2. The analysis also gives further insight into existing algorithms with attributes similar to those covered in the analysis. More detailed explanation of this analysis is given in the available publication mentioned at the end of this page.

An analysis of Sorting data arranged as 2-Dimensional Array

This discussion paper gives an in-depth analysis of sorting a set of data values structured as a 2-dimensional grid. The sorted 2-D grid is traverse in row major lexicographic order. The discussion looks at
(1) the difference between Column followed by Row (CR) sorting and Row followed by Column (RC) sorting,
(2) the difference in the distribution of inversions as a result of Column sort as opposed to Row sort,
(3) the distribution of data values in a CR, RC or Right to Left (RL) diagonally sorted array relative to their final sorted location in the lexicographic sorted array,
(4) the probability of achieving a complete sort in lexicographic order after a Column-Row or Row-Column sort,
(5) the distribution of inversions in a CR, RC or RL diagonal sorted 2-D array among other issues.

We also presented a set of 2-dimensional sorting algorithms that creates a sort in row-major lexicographic order after a CR, RC and/or RL diagonal sort on a 2-D set of data values. A scattering algorithm is presented at the end of the discussion, which is then used to achieve a 6-steps column and row operations to achieve a sort in lexicographic order. Some section of the analysis also demonstrates the correctness of J. M. Marberg & E. Gafni algorithms without the use of the zero-one principle. Some of our results can be generalised for data arranged in a m-dimensional grid. Where m is some positive integer > 2.

Our results shed some insightful hint on h-ordering as used in Shell-sort and similar algorithms such as Batcher's Odd-even merge-sort. I use these results in a generalisation later to develop an argument about m-dimensional sorting, from which I derive the following results.

In fact, I have just completed a write up for a merge-sort algorithm base on this generalisation that is in-place and stable. Asymptotic analysis on the operational complexity indicates that the algorithm does 1.082Nlog2(N)-1.706N compare/ exchange operations to sort N data values. The algorithm can also be implemented on a parallel network to do sorting in O(log2(N)) time with small proportionality constant. I then show a similar but unstable algorithm that does sort in Nlog2(N)-O(N) compare/exchange operation always and that can be implemented on a parallel network system using log2(N) steps or on a O(log2(N)) multiprocessor system with O(N) interconnection.. In fact, I derive a general solution to the network sorting problem and I show you a network that will do 59 compare/exchange operations to do sort on 16 values.


Page 5 of 7
Information about in-place merge Information about Kronrod's merge technique