[anonymous26]

macosxnerd101, on 06 December 2010 - 03:42 PM, said:

O(n) is worst case for memory usage, not runtime. Worst case runtime is O(n log(n)).

Yes, quite right. I did say a 'quick look' and I have more important things to remember than merge sort efficiency.

Anyway, any better suggestions on Merge Sort?

This post has been edited by ButchDean: 06 December 2010 - 10:01 AM

[Nikitin]

ButchDean, on 05 December 2010 - 04:41 PM, said:

Merge Sort immediately came to my mind. With a a million 32-bit integers you cannot be looking at anything worse than O(n). That would be insane!

I know, merge sort took a whopping 2 seconds to sort a million 32-bit integers on my old Pentium! Oh the humanity!

ButchDean, on 06 December 2010 - 09:37 AM, said:

Just glancing at Wikipedia it has an average case of O(n log n) with a worse case of O(n), hence my suggestion of its use.

Quote

Yes, quite right. I did say a 'quick look' and I have more important things to remember than merge sort efficiency.

Like remembering what big-O is, and how it works?

=========

Sorry, I'm under a lot of stress this week.

[anonymous26]

No, no I won't forget!

[tek1]

ButchDean, on 06 December 2010 - 09:37 AM, said:

Just glancing at Wikipedia it has an average case of O(n log n) with a worse case of O(n), hence my suggestion of its use.

Ignoring the fact that you had mistaken worst-case space for worst-case time, your deduction wouldn't make sense because the average case -- O(n log n) -- is greater than what you had believed to be the worst case -- O(n). (The worst case can't be less than the average case)