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 log2(N) levels of recursion. It is interesting to compare quick sort with merge sort; the former has a pre-order structure the latter a post-order structure. In fact there is also a bottom-up, breadth-first 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 time-complexities 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 "working-space array" and log(N) for the stack space. A naive non-recursive 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 non-recursive 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 in-situ 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. |
|
|