Softpanorama (slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-)

Mergesort

MergeSort is a stable algorithm (preserves original order of records with equal keys) that has speed comparable to the best unstable algorithms (shellsort and heapsort).  Like HeapSort, easily adapted to any data type and guaranteed to run  in O(N log N) time. On the down side it needs an extra array of N items, but these can be pointers if the keys themselves are larger than pointers.

The value of softing algorithms changes with the development of hardware. With cheap memory and large RAM sized
(1-2G) typical for Vista class PCs, mergesort might be a substantially better algorithm then quicksort.

As Paul Hsieh (the author of  a contrarian article (2004) that investigated the actual behavior of heapsort, quicksort and mergesort on large sample of data) aptly observed :

Mergesort kind of combines the good features of quicksort and heapsort. It is also context insentively recursive, so small cases are a major leverage point for overall performance as well. However, it also is recursive in a static way, so that it cannot vary or be caught in bad cases where it might perform uncharacteristically badly. The problem with Mergesort is that every element will move lg(n) steps (or perhaps a few less because of the exploitability of direct sorting of small sub-lists) regardless. So the average, worst and best case running time is identical no matter what.

Like quicksort it is a divide and conquer algorithm and according to  Paul Hsieh it has similar number of comparisons:

Only this time all the work is done when combining the pieces together. Divide phase consists of merely splitting the sequence in half evenly. Final test is trivial, since a one-element list is still automatically sorted. Combine takes two lists, each sorted in ascending order and combines both of them into one sorted list.

Recommended Links

TalkMerge sort - Wikipedia, the free encyclopedia

Mergesort (/www.iti.fh-flensburg.de)

11.4 Mergesort

merge sort

MergeSort demo with comparison bounds

Mergesort Introduction

This page demonstrates MergeSort. At the same time, it shows the number of comparisons actually used, and a worst case upper bound on this number.

Contents:

• Description of MergeSort
• Time bounds
• An expression for T(n)
• Recursive definitions and recurrence relations
• T(n) for particular n
• MergeSort in action
  • What's happening, and what are those colours?
  • What are those numbers?
  • Trying other inputs
• Further explorations
• Feedback

Last modified: February 28, 2008