Nested sorting class of array sorting algorithms

[Namir]

Hi All,

I recently found the GeeksForGeeks.com web site and it had listed, among others, a long set of sorting algorithms. Moreover, that web site presents implementations for the sorting algorithms in different programming languages, like C++ and Python 3. I decided to tinker with the subject and came out with a somewhat new general approach—nested sorting which is a divide-and-conquer scheme. The general idea behind nested sorting is to divide the big array to sort into buckets (or pages). They have equal sizes (except for the last bucket in most cases). The general approach is:

1. Sort the elements in each bucket by applying a sorting algorithm. You end up with buckets, each containing a sorted sub-array.

2. Apply the same (or even different) sorting algorithms to the buckets. When comparing two buckets you compare the last element of the first bucket with the first element of the second bucket. If they are in order, then the buckets are in order. Otherwise you do a merge-sort of the sub-arrays and write the ordered sub-arrays back in the source bucket. This phase involves comparison of elements, but not traditional swapping, as the merge-sort step writes, in order, the elements from the two sub-arrays into a temporary array. Finally the values from the temporary array are written back to the source sub-array memory spaces.

Nested sorting algorithms require fewer comparisons and swaps. The improvement brought by applying the nested sorting scheme is more effective with less efficient sorting algorithms.

The nested sorting scheme works very well (with the sub-arrays in the buckets and with the buckets) with algorithms like Bubble sort, Shell Sort, Comb Sort, and other algorithms that compare and swap near/distant neighboring elements.

For algorithms, like Selection Sort, sorting the buckets requires a modified version of the basic sort algorithm. This difference is to the fact that this kind of algorithm attempts to scan the (sub)array and locate the appropriate location of a targeted element. In other words, steps that involve scanning elements can impose a hurdle for implementing the nested sorting scheme with that basic sorting algorithm.

I would not be surprised if the nested sorting scheme hits some walls where it cannot easily applied, or applied at all, with certain sorting algorithms. I have not explored this impasse yet. It’s just a hunch for now!

I am developing some Matlab code for examples using the nested sorting scheme and plan to publish a report on my web site within a month. So stay tuned! I will publish the report on my web site and provide a link on this site.

Namir