Merge Sort

[ Follow Ups ] [ Post Followup ] [ CS2604 Discussion WWWBoard ] [ FAQ ]

Posted by DarkTerritory on August 05, 1999 at 00:21:04:

The only sort on the project that is still bothering me is the merge sort.

Invariably, I get n-1 comparisons.

I am using code loosely based on that which is printed on 131 and 132.

Note that in both cases, according to the ruling that you only count comparisons of elements not of counters, the only line that results in a count is the fourth from the end.

When you think about it, it makes 100% perfect sense that you would get n-1 executions of this statement.

So needless to say, n-1 in no way looks like n log n and is not a good comparison to anything else, since much of the work gets eaten up copying numbers between arrays.

Is there something else that should be counted in this sort?

-DT

Follow Ups:

Post a Followup

Name:
E-Mail:

Subject:

Comments:
: The only sort on the project that is still bothering me is the merge sort. : Invariably, I get n-1 comparisons. : I am using code loosely based on that which is printed on 131 and 132. : Note that in both cases, according to the ruling that you only count comparisons of elements not of counters, the only line that results in a count is the fourth from the end. : When you think about it, it makes 100% perfect sense that you would get n-1 executions of this statement. : So needless to say, n-1 in no way looks like n log n and is not a good comparison to anything else, since much of the work gets eaten up copying numbers between arrays. : Is there something else that should be counted in this sort? : -DT

Optional Link URL:
Link Title:
Optional Image URL:

[ Follow Ups ] [ Post Followup ] [ CS2604 Discussion WWWBoard ] [ FAQ ]