[k_l_s]

Given two sorted lists A and B concatenated as a single list AB:

Divide the list up into sqrt(n) pieces, each of size sqrt(n). Create one such piece consisting of the sqrt(n) largest elements of the combined list and move this piece to the left-most position (call this the buffer piece), while the remaining pieces are simply formed from the remaining elements. Note that the remaining pieces will retain their ordering from the fact that A and B were originally sorted (as long as care is taken not to cross the boundary of A/B), while the left-most piece need not be sorted at this point. Stable? [I didn't see it in the paper, but I think it's necessary] sort the sqrt(n)-1 non-leftmost pieces in non-decreasing order by their tail element. Finally, merge (details left out as to when to stop the merge) the longest sequence of pieces constructable from the beginning of the un-merged list so that the tail element of any piece is not greater than the head element of it's downstream piece with this sequence's downstream piece, using the left-most piece as the buffer and swapping the min element of the two lists into the min buffer position instead of overwriting the buffer element. After a merge, the buffer piece will remain as a single piece and may be re-used as the buffer for the next merge. In the end, simply sort the buffer piece. Notice that we may use an O(n^2) sort for the two sorts that we need to perform without breaking the merge's linear time property since in both cases we're sorting sqrt(n) items.

The min element of the remaining pieces will always make its way into the min buffer position a sorted lists' pieces will not be re-ordered by the tail-element sort.

Anyhow, many details left off, but you asked for a gist and I believe that this qualifies as a gist.