
Kway merge sort problem
If you'd sort an array of data using a kway merge sorting algorithm, you would divide your array in k pieces. Then recursively call the method on every piece, where if the piece can still be divided into k pieces, repeat, and once it cannot(size<k), sort the remaining piece with quicksort.
You could put every piece in its own array, or keep them in the same input array. If you choose the first option, you have a lot of extra space used, while with the second option, you don't know the boundaries of the pieces unless you put those in an auxiliary array as well. Especially with arrays that have a remainder when divided by k this will give trouble and prevent you from effectively using one formula for finding all boundaries.
Is there an elegant solution for this, that does not use a lot of extra space and is efficient in terms of used comparisons?