If S is a sorted list (represented by doubly-linked list datastructure) of length n=k * k so that k=sqrt(n) is an integer, we can partition S into k smaller sorted lists each of length k. By constructing an auxiliary list B (a doubly linked-list specifically) which contains pointers into the first element of each partition of S we can then perform sorted-insert of an element into S in O(sqrt(n)) time. now i need to use this idea to give an algorithm for sorting an unsorted list L in O(n*sqrt(n)) time. as i see it we need to add each element of L to a new list S and for each insertion ensure that S remains sorted. problem is to do this we need to compute B each time which takes theta(n') (where n 'is number of elements of S so far). Moreover we cannot be sure that n' is a perfect square so how to partition S?