Skip to main content
4 of 11
added 899 characters in body
thepacker
  • 893
  • 7
  • 11

The normal merge sort algorithm - merge step with normally apply n + m -1 comparisons, where one list is of size n and and the other list is of size m. Using this algorithm is and in most simplest approach to combine two sorted lists.

If the comparisons are too expensive you could do two things - either you minimize the number of comparisons or you minimize the cost of comparisons.

Let's focus on the minimization of the cost of comparison. You and only you can decide whether the data are you are comparing can be quantized or not. If you can quantize them, which is a form of implementing a hash method, which is keeping the ordering. E.g. if your Data is compared by Name, Then the first tname, ... you can take the first to Chars of the name "Klaehn, Ruediger" and reduce/quantize your data element to "Kl.Ru", if you compare it to "Packer, The" you preserve the ordering "Pa.Th" - you can now apply a cheaper comparison algorithm, comparing the reduced values. But if you find another "Kl.Ru", you now have a near value, and you might now switch to a more expensive approach.

If you can extract this quantized value faster from your data, than comparing it, this is the first thing you do, you compare the quantized or hashed value first. Please keep in mind, that this value needs to computed only once, so you can compute it on creating the data element.

I also mentioned another way, to minimize your comparisons.

I had a look into the classic book TAOCP- Volume 3-Sorting and Searching, (pp.197-207, section 5.3.2) which has full 10 pages on this topic. I found two references to algorithms which are faster than n+m-1 comparisons.

First there is the Hwang-Lin merge algorithm, and the second an improvement by Glenn K Manacher () - both are cited by TAOCP as well as an algorithm by Christen, which approaches the lower bound of needed coparisons on special conditions on the length n and m of the lists.

(editing...)

thepacker
  • 893
  • 7
  • 11