Merge Sort 

Merge sort divides the array into two halves which are sorted recursively and then merged to form a sorted whole. The array is divided into equal sized parts (up to truncation) so there are log_{2}(N) levels of recursion. It is interesting to compare quick sort with merge sort; the former has a preorder structure the latter a postorder structure. In fact there is also a bottomup, breadthfirst merge sort.
Change the data in the HTML FORM below, click `go', and experiment;
the section processed by each recursive call is
ComplexityTimeThe best, average and worst case timecomplexities of the (basic) algorithm are all the same, O(N*log(N)). SpaceThe space complexity of the recursive algorithm is O(N+log(N)), N for the "workingspace array" and log(N) for the stack space. A naive nonrecursive translation would still use O(N+log(N)) space, log(N) being for an explicit stack. However, because the array sections vary in a simple and systematic way, there is a nonrecursive version that does not need any stack and requires O(N) space only (but there again, log(N)<<N, if N is large). There are in fact insitu merging algorithms that only use O(1) space but they are difficult! StabilityMerge sort is stable if written carefully, it is a matter of a `<=' versus a `<'. Notes
© L.A., Department of Computer Science UWA 1984, Department of Computer Science Monash 1986, and (HTML) Comp. Sci. & Software Eng., Monash University 1999. 

