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

[ttw]

This is equivalent (in the general case) to one of the merge sorts. These are as efficient as it gets with comparison based sorting. The binary version sorts a bunch of short arrays (or buckets) by whatever method is efficient for short arrays. Then the arrays are merged pairwise to grow their lengths. (If the starting arrays are differing size, merging from the smallest is best. This isn't usually mentioned.)

[Paul Dale]

I think this will fall out as O(n log n) time and O(n) storage. However, the constant terms will be large. The temporary buffers in the merge phase guarantee two copies for every item for every merge. For the final merge of two half lists, it requires O(n) storage. On the other hand, quicksort requires O(log n) additional storage and takes O(n log n) time on average. It also doesn't double copy.

The sorting wars were essentially resolved in the 1970s. There are some interesting parallel sorts but my favourite is this one.

If you've not watched these before, have fun.


Pauli

[Albert Chan]

(02-16-2020 04:27 AM)Namir Wrote:  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.

Any difference to Timsort ?

https://hackernoon.com/timsort-the-faste...b28417f399

[Namir]

(02-16-2020 12:42 PM)Albert Chan Wrote:  Any difference to Timsort ?

https://hackernoon.com/timsort-the-faste...b28417f399

I will look at it. Thanls for the link.

Namir