Algorithm for splitting an array into k sub-arrays
Insert$(x)$ can be implemented in $O(k \log(n/k))$ time. I will use the terms subarray and group interchangeably. 

Let $n$ be the number of elements in the data structure before the insert operation. We will maintain this invariant: each subarray contains either $\lfloor n/k \rfloor$ or $\lceil n/k \rceil$ elements. The elements of each subarray are stored in a min-heap and in a max-heap that support element deletion.

Insert $x$ into the unique group $i$ whose minimum element is smaller than $x$ and such that the minimum element of the next group (if any) is larger than $x$.

Notice that if, before the insert operation, $i$ contained $\lfloor n/k \rfloor$ elements then the operation cannot possibly violate the invariant.
This means that if the invariant is violated then $\lfloor n/k \rfloor &lt; \lceil n/k \rceil$, $i$ contained $\lceil n/k \rceil$ elements, and there is a group $j \neq i$ that contained $\lfloor n/k \rfloor$ elements.
Let $j^*$ be the value of $j$ that satisfies the above conditions and minimizes $|j^*-i|$.

We can restore the invariant as follows:


If $j^* &lt; i$ then all groups $h \in \{j^*+1, \dots, i-1\}$ have $\lceil n/k \rceil$ elements. For each $h= j^*+1, \dots, i$ do the following: pick the minimum element $m$ from group $h$ (this can be done in $O(\log n/k)$ time by a pop() operation on the min-heap of $h$ and a delete($m$) operation on the max-heap of $h$) and add $m$ to group $h-1$ (this amounts to adding $m$ to both the min-heap and the max-heap of group $h-1$).
If $j^* &gt; i$ then all groups $h \in \{i+1, \dots, j^*-1\}$ have $\lceil n/k \rceil$ elements. For each $h= i, \dots, j^*-1$ do the following: pick the maximum element $M$ from group $h$ and add it to group $h+1$.