2
$\begingroup$

Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption? While I understand the standard analyses of asymptotical behavior of number of comparison operations, I don't quite understand why other costs of other types of operations are negligible.

[Edit 2014-08-26]

If I run the same mergesort implementation on two different computers (with possibly different architecture etc.), how to argue that running time of mergesort divided by the number of compares will approach (possibly different) constants as the problem size increases?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ In addition to the older version of this question, some of our reference questions may be interesting for you. $\endgroup$
    – Raphael ♦
    Aug 20, 2014 at 5:44
  • $\begingroup$ @Raphael From what I read in the link you put, I don't think this is a duplication. The question asks why not considering other costs such as (moving an element in the array from on position to another), why ignore these costs? In case such as sorting primitives array, the cost of comparison is so small that the relocating cost is actually a source of concern. In fact, quick sort works very well because when comparison cost becomes so low, writing and reading elements start coming into the picture... $\endgroup$
    – InformedA
    Aug 21, 2014 at 9:09
  • $\begingroup$ .. in fact, a good answer to this question might potentially address speculation of the benefit of serial reading of elements in array that make quick sorts better than merge sort. In modern CPU with pipelining and super-scalar, putting things in big serial chunk help increase throughput greatly which helps the final running time. Even in the case of a modification of merge sort such as Tim sort used by Java JDK to sort objects, one can see the same pattern of reading things in big serial chunk to take advantage of hardware implementation... $\endgroup$
    – InformedA
    Aug 21, 2014 at 9:12
  • 2
    $\begingroup$ @randomA This question makes only sense if it is, "In basic theoretical analysis, why do we...?" (since the premise does not hold elsewhere). This question has been answered comprehensively in the question I linked. Now, the fact that this model is problematic in terms of what it tells us about real runtimes is known and very interesting. A question like "What do I have to consider for predicting sorting runtimes on real machines?" would be great and not a duplicate, afaict -- but it's not this one. $\endgroup$
    – Raphael ♦
    Aug 21, 2014 at 9:57
  • 1
    $\begingroup$ @randomA While the two questions are not strictly speaking exact duplicates, the answers to the earlier question cover this aspect very well (better than the answers posted here so far), so in the interest of keeping the best available answers associated with this question, it is best to leave this question closed as a duplicate. The other points that you raise could make interesting answers, but as Raphael notes, they would not be answers for this question but for a related one (which you are welcome to ask). $\endgroup$
    – Gilles 'SO- stop being evil'
    Aug 21, 2014 at 14:15

2 Answers 2

Reset to default
1
$\begingroup$

It mostly has to do with the nature of the algorithm. In selection or insertion sort, for example, the important work is the number of comparisons: the extra loop overheads are subsumed in the calculations. In essence, as @bellpeace noted, you add a loop operation with each comparison, so in the long run you're only adding a constant multiple to the work done. This would be different if you were considering, say, radix sort, where you aren't comparing elements but rather their bit values, which you can do without comparisons (more or less).

Improve this answer
$\endgroup$
1
$\begingroup$

Because the number of comparisons dominates the number of other operations. Since costs of all operations are usually pretty much the same (within a constant factor), costs of non-comparison operations get eaten by constants in the asymptotic measure.

Improve this answer
$\endgroup$

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