What is the worst-case time for insertion sort within merge sort?

Question

Recently I stumbled upon this problem from Introduction To Algorithms Edition 3

Problem 2-1:

Although merge sort runs in O(n logn) worst-case time and insertion sort runs in O(n^2), the latter runs faster for small problem sizes. Consider a modification to Merge Sort in which n/k sublists of length k are sorted using insertion sort and then merged using standard merging mechanism.

(A) Show that insertion sort can sort the n/k sublists, each of length k, in O(nk) worst-case time.

---

The answer given is:

Ans: Insertion sort takes (k^2) time per k-element list in the worst case. Therefore, sorting n/k lists of k elements each takes (k^2 n/k) = (nk) worst-case time

How do they get (k^2 n/k) from the given data?? Im not understanding this at all and would greatlly appreciate an explanation.

Answer 1

The sublists are of length k, therefore insertion sort takes k^2 for each sublist. now, there are n/k sublists in total, so, n/k * k^2 is nk. The key understanding here is that there are n/k number of sublists, and insertion sort takes k^2 time to sort each one.

Another thing to note, is that knowing that merge sort has O(n logn) is actually not important at all to this problem, because they don't ask for the time for sorting the whole list, just the time for sorting all of the sublists.