[Daskill]

I'm having trouble understanding merge sort. Can anyone explain it to me?

[-Fabez-]

http://www.cprogramming.com/tutorial...mergesort.html Explains how it works in C, I have never used a merge sort, but it is explained clearly in the webpage and should be generic for all programming languages.

[Daskill]

I'm a little confused, what does it mean if it is O(nlog(n)) complexity?

Also, if I am sorting by merge sort and have a group of three values I have to split up, do I split it up so I have the single value first, then the two values, or do I do it the other way round?

So if I've got (13, 6, 7), does it then become

(13), (6,7)

or

(13,6), (7)

?

[BrutalB]

O(nlog(n)) is the running time of the algorithm... Merge sorting is a very efficient way of sorting (compare the Big Oh values to other sorting algorithms)... And as far as I know, it doesn't matter which way round you go with the 13, 6 and 7 or 13 and 6, 7...

Any corrections are welcome, that's what I remember from my Datastructures and Algorithms classes

[BobFoster]

The two halves of the sort are treated identically, so it doesn't matter which half has the more entries if you have an odd number of elements to sort. You only need lists of similar length anyway when splitting; the exact number of elements is not actually important.

O(n log n) is an indication of the efficiency of the algorithm, as BrtualB has already said. Specifically, n refers to the number of items in the list you're sorting and O(50) would mean the sort takes 50 steps to complete. The O() value is often called the complexity.

Sorting algorithms can usually be classified with an average and worst case complexity and Merge Sort has O(n log n) for both average and worst. If you compare this with other common algorithms: Quicksort, O(n log n) average but O(n^2) worst case and Bubble sort, O(n^2) in both cases, you can see that of the three it is the best. Work out a few O values for large numbers of items and you'll see exactly how much more efficient it is than a bubble sort, for example.

Hope this makes sense.

Regards,
Bob