1
$\begingroup$

MergeSort has two parts, "divide" and "merge" (arguably three if you include "recurse" as its own part in the middle). I'm interested in the "merge" part, which tends to look like this:

consider two priority queues list1, list2
initialize an empty sorted list
while neither list1 nor list2 is empty:
    find lowest element between peek(list1) and peek(list2)
    pop that element from its list and add it to the sorted list
add the rest of the non-empty list to the sorted list
return the sorted list

This paradigm of "split into multiple priority queues and continuously handle the first elements" is also useful for problems that decidedly do not involve merging, such as performing operations on one list depending on the highest-priority element of another list that's less than it. For example,

consider two priority queues list1, list2
initialize an empty destination list
while neither list1 nor list2 is empty:
    while peek(list1) < peek(list2):
        add f(peek(list1), peek(list2)) to destination list
        pop element from list1
    pop element from list2
return destination list

In both of these examples, the same idea of "iterate through multiple priority queues simultaneously, doing something with the top elements of each, but only pop one of them at a time" is used. This is different than matching two lists and enumerating through corresponding elements.

Is there a specific name for this technique/paradigm? The Wikipedia page for MergeSort does not, at time of writing, answer the question, and in the context of MergeSort I've never seen it described as anything other than "merge" (which is inaccurate in my second example) or "conquer" (which is too vague).

$\endgroup$
  • 2
    $\begingroup$ I would call it merging. $\endgroup$ – Yuval Filmus Aug 29 at 7:13
  • $\begingroup$ It is called merge. Thus the name: sort by merging. $\endgroup$ – vonbrand Aug 29 at 14:49
  • $\begingroup$ Well, yes, but I was asking in the context of other applications. My second example uses the same paradigm but clearly does not involve merging anything. $\endgroup$ – Green Cloak Guy Aug 29 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.