sort array to k sorted parts of unsorted element

Question

I need an algorithm that, given an array and an int k, returns an array that is k "parts" of numbers and:

• The "parts" are ordered. meaning that if a number is in "part" j, it is smaller than every number in "part" i for i > j.

• The elements in a "part" are not necessarily ordered.

FYI, this is NOT a k-sorted problem! I can't find anything about it. Every search returns only k-sorted algorithms and discussions.

Answer 1

One answer would be to simply sort the array and then split it into chunks, e.g. in psuedocode:

sorted_arr = sorted(arr)
new_arr = []
arr_len = size(arr)
chunk_len = max(1, floor(arr_len / k))
for (i = 0; i < arr_len; i += chunk_size) {
    new_arr.push(sorted_arr.slice(i, i + chunk_len));
}

But I'm guessing you're looking for a solution faster than actually just sorting the array first and then chunking.