k_l_s

This has to be one of the most exploited (mis?)conceptions of the 21st century. Doctors, employers, websites, software plugins, account agreements, almost everything with which one interacts in the normal course of a modern life has a massive privacy statement that, using the unnatural jargon of the law as a gate, makes unreasonable statements which destroy the rights of the consumer and create rights for the provider. I recall a recent trip to the eye doctor where the standard document made the statement that I pre-consent to any and all treatment that the doctor orders and pre-agree to be financially responsible for all such treatments in case my insurance does not pay. My guess is that most of us have inadvertently pre-consented our finances and other aspects of our lives to various companies via these statements buried within the haystack of legalese that must be "signed" in order to operate a 21st century life.

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.