0

Today I was corrected for mentioning "External Merge Sort" as an example of a divide-and-conquer (D&C) algorithm and after doing a lot of research online and in the most prominent books on algorithms, I started to realize that External Merge Sort is usually placed in their own separate categories and never referred to as a D&C algorithm.

Given that Merge Sort is one of the most famous examples of a D&C algorithm, how come that External Merge Sort is not considered D&C algorithms in most books?

Improve this question
3
  • 1
    "that External Merge Sort is not considered D&C algorithms in most books"? Which books? I doubt that, maybe its just a misconception of yours? I guess "most books" describe Merge sort as a D&C algorithm, so its implicitly clear that "External Merge Sort" belongs also to that category.
    – Doc Brown
    Jun 24, 2015 at 6:06
  • You're right, "most books" was too vague. I was referring to the Cormen, Rivest, et al "Introduction to Algorithms" and to the 3rd volume of Knuth's "The art of computer programming". Also, wikipedia and most web pages describing external merge sort seem to avoid the words "divide-and-conquer". Is there something specific to external merge sort that makes it not a D&C algorithm?
    – Mike Laren
    Jun 24, 2015 at 6:21
  • 2
    I think you are overinterpreting this. Since Merge sort is already described as a D&C algorithm, I think those books do not bother to mention that "External Merge Sort" is also D&C, because its pretty obvious. And when they discuss External Merge Sort, the focus is typically on having an example for an external sort algorithm, mentioning it is still D&C would be completely insignificant in that context.
    – Doc Brown
    Jun 24, 2015 at 8:48

1 Answer 1

Reset to default
1

Personally I don't know the reasoning behind those books and I don't claim to have any unique insight on this issue.

However, external merge sort can be implemented in exactly two stages, and neither stage contain recursive subdivision. In other words, in both stages, there is only one level of subdivision.

Choose number of subdivision N.

Stage 1: Arbitrarily partition input data into N subdivisions. Sort within each subdivision.

Stage 2: Create N FIFO queues, each feeding from the corresponding subdivision in the sorted order. Perform N-way mergesort (binary heap or selection sort) by peeking each queue's head and removing the smallest element, sending it to the output FIFO queue. Whenever an FIFO queue become empty it will feed from the remaining data from the corresponding subdivision. The sizes of FIFO queues are chosen according to available memory, but the algorithm still works correctly even if all FIFO queue has size 1.

As explained above, there is no recursive subdivision of the problem.

This is just an observation. I don't know whether book authors regard recursive subdivision as a key part of D&C.

There are many external merge sort schemes. The one described above is only one example. Those other schemes might make use of recursive subdivision. I don't know much about those so I won't be able to comment.

Improve this answer
6
  • Isn't "Sort within each subdivision" a recursive subdivision?
    – Idan Arye
    Jun 24, 2015 at 9:59
  • @IdanArye The sorting performed within each subdivision is tangential to the main concept of external sorting. In fact, for certain types of data, the sorting within each subdivision might not even be an O(N log N) sorting algorithm.
    – rwong
    Jun 24, 2015 at 10:02
  • But any recursive solution can be modified that way - replace the recursive call with a call to another algorithm that does the same job. This artificial modification does not change the D&C nature of the algorithm - a simple solution to the bigger problem that relies on solutions to parts of it.
    – Idan Arye
    Jun 24, 2015 at 10:12
  • @IdanArye If the algorithmic nature of the macroscopic solution and the microscopic solution are different, and neither solutions involve a recursive application (not necessary in the form of function calls) of its own likeness, then it is not recursive. The phrase "divide and conquer" is often used as an allegory to the mental processes involved in problem-solving. However, the original post asks about the opinions of algorithmists.
    – rwong
    Jun 24, 2015 at 10:17
  • I do not think there is a "mathematically strict" or "legal" defintion of what D&C is or is not. However, to my understanding, the focus of that term is on "Divide" (split problem in equally sized subproblems until the subproblem is small enough to be solved on its own) and "Conquer" (combine the results of the subproblems), and not on "recursion".
    – Doc Brown
    Jun 24, 2015 at 10:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.