for(inti = 0; i < data.Length; i++)for(intj = 0; j < data.Length - 1; j++)if(data[j] > data[j + 1]) { tmp = data[j]; data[j] = data[j + 1]; data[j + 1] = tmp; }

1st line (outer for loop) should be

for(inti = 0; i < data.Length - 1; i++)

2nd line (inner for loop) should be

]]>for(intj=0; j < data.Length - i - 1; j++)

Not mentioned in the tutorial is bottom up (iterative) merge sort, which skips all of the recursion, and simply considers a data set of n elements as n runs of size 1, and begins by merging runs, until the merging produces a single sorted run, which will be the sorted data set. Normally the merging is done left to right, doubling the size of runs on each pass. Variations of iterative merge sort are how most library versions of merge sort are implemented (like timsort).

Despite favorable cache locality for a few of the levels of recursion versus iterative passes, iterative merge sort tends to be a bit faster than top down, but not by much since most of the time is spent merging versus generation of indices (or pointers) via recursion versus iteration, and the merging can be identical for top down and bottom up merge sort.

Legacy versions of merge sort dating back to the days of tape drives are iterative merge sort or a variation called polyphase merge sort. I'm not sure when or why recursive top down sort became popular.

Wikipedia's article on merge sort includes simple (non optimal) examples of recursive and iterative merge sort for arrays as well as linked lists.

http://en.wikipedia.org/wiki/Merge_sort]]>

Merge sort on objects is primarily done for stability, but it's also usually faster. In terms of performance, merge sort does more moves but fewer compares than quick sort or a variation of quick sort like intro sort. In the case of an array of pointers to objects, typically only the pointers are moved, while comparing objects requires dereferencing via the pointers, increasing the overhead for compare. The end result is merge sort is usually faster at sorting an array of pointers to objects than quick sort or a variation of quick sort.]]>

data[i] = h.RemoveLowest();

Wrt,above snippet of code that was used in example for Heapsort.

The author takes data from data array, makes a heap structure out of it stored in h structure.

Finally while storing the sorted array by using h.RemoveLowest();

the sorted output can be stored back in the input array data, in that case the statement int[] result = new int[data.Length];

is not needed.

If one wants to preserve unordered input array data , then the data is to be written to the allocated result array.

Allocating result array , but storing output back in data array is inefficient.

Regards

Dilip]]>

He didn't mention O(1) extra space (apart from the array).

The old array is used to store the sorted array, so I would agree with O(1) extra space, but the algorithm still needs O(N) in total.

edit: typos]]>

* from heap in x[0..i-1], x[0] is removed and the heap is popped

* x[i-1] := temp;

obviosuly storing a number needs O(1) space]]>

The animation here is pretty, http://en.wikipedia.org/wiki/Heapsort]]>