Adaptive Sort

Merge sort

Merge sort is an O(n log n) comparison-based sorting algorithm. In most implementations it is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It was invented by John von Neumann in 1945.

Conceptually, a merge sort works as follows:

Merge sort in action
  1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
  2. Divide the unsorted list into two sublists of about half the size.
  3. Sort each sublist recursively by re-applying merge sort.
  4. Merge the two sublists back into one sorted list.

 

Merge sort incorporates two main ideas to improve its runtime:

  1. A small list will take fewer steps to sort than a large list.
  2. Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they're already sorted (see the merge function below for an example implementation).

For a more complete description, see the entry about Merge sort in Wikipedia (text and picture are borrowed from that site).

Source Code

An efficient implementation in C#.NET

In order to compare ASort to well known algorithms, I implemented an efficient version of Merge sort in C#.NET. My version requires Θ(n) in memory consumption, but uses alternating buffers and other tricks to minimize the need for copying arrays of values back and forth. You can see how this implementation compares to quicksort and ASort on the performance page.

Below is the C#.NET source code. Feel free to use it for whatever purpose you like (cut-and-paste or use this link to get source code).

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace MergeSort

{

    public class MergeSort<myType>

    {

        // Main sort method

        public void Sort(myType[] arr, Comparison<myType> comp)

        {

            myType[] buffer = new myType[arr.Length], originalBuffer = arr;

            MergeSortNonRecursive(arr, 0, arr.Length - 1, buffer, comp);

        }

 

        // Non recursive implementation (its a little faster than the recursive one)

        private void MergeSortNonRecursive(myType[] arr, int lo, int hi, myType[] buffer, Comparison<myType> comp)

        {

            int m = 1, n = hi + 1, i, stop2 = 0;

            myType[] pTmp, originalBuffer = arr;

 

            while (m <= n)

            {

                i = lo;

                while (i < n - m)

                {

                    if (m == 1)

                    {

                        if (comp(arr[i], arr[i + 1]) == 1)

                        {

                            buffer[i] = arr[i + 1];

                            buffer[i + 1] = arr[i];

                        }

                        else

                        {

                            buffer[i] = arr[i];

                            buffer[i + 1] = arr[i + 1];

                        }

                        stop2 = i + 1;

 

                    }

                    else

                    {

                        stop2 = (i + 2 * m > n ? n : i + 2 * m) - 1;

                        Merge(buffer, arr, i, i + m - 1, i + m, stop2, i, comp);

                    }

                    i += 2 * m;

                }

                if (stop2 < n - 1)

                    Array.Copy(arr, stop2 + 1, buffer, stop2 + 1, n - stop2 - 1);

                pTmp = buffer;

                buffer = arr;

                arr = pTmp;

                m *= 2;

            }

            if (arr != originalBuffer)

                Array.Copy(arr, originalBuffer, n);

        }

 

        // Merges 2 arrays into one sorted array

        private void Merge(myType[] buffer, myType[] arr, int ind1, int stop1, int ind2, int stop2, int iBufferOffset, Comparison<myType> comp)

        {

            for (; ; )

            {

                if (comp(arr[ind1], arr[ind2]) == 1)

                {

                    buffer[iBufferOffset++] = arr[ind2++];

 

                    // Copy the rest of the elements from other array

                    if (ind2 > stop2)

                    {

                        if (ind1 < stop1 - 2)

                            Array.Copy(arr, ind1, buffer, iBufferOffset, 1 + stop1 - ind1);

                        else

                        {

                            buffer[iBufferOffset] = arr[ind1];

                            if (ind1 < stop1)

                            {

                                buffer[iBufferOffset + 1] = arr[ind1 + 1];

                                if (ind1 < stop1 - 1)

                                {

                                    buffer[iBufferOffset + 2] = arr[ind1 + 2];

                                }

                            }

                        }

                        return;

                    }

                }

                else

                {

                    buffer[iBufferOffset++] = arr[ind1++];

 

                    // Copy the rest of the elements from other array

                    if (ind1 > stop1)

                    {

                        if (ind2 < stop2 - 2)

                            Array.Copy(arr, ind2, buffer, iBufferOffset, 1 + stop2 - ind2);

                        else

                        {

                            buffer[iBufferOffset] = arr[ind2];

                            if (ind2 < stop2)

                            {

                                buffer[iBufferOffset + 1] = arr[ind2 + 1];

                                if (ind2 < stop2 - 1)

                                {

                                    buffer[iBufferOffset + 2] = arr[ind2 + 2];

                                }

                            }

                        }

                        return;

                    }

                }

            }

        }

    }

}