Nested sorting class of array sorting algorithms

[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