Merge Sort

Conceptually, a merge sort works as follows:

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

Merge sort incorporates two main ideas to improve its runtime:

• A small list will take fewer steps to sort than a large list.
• 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).

public IList MergeSort(IList a, int low, int height)
{
    int l = low;
    int h = height;

    if (l >= h)
    {
        return a;
    }

    int mid = (l + h) / 2;

    MergeSort(a, l, mid);
    MergeSort(a, mid + 1, h);

    int end_lo = mid;
    int start_hi = mid + 1;
    while ((l <= end_lo) && (start_hi <= h))
    {
        if (((IComparable)a[l]).CompareTo(a[start_hi]) < 0)
        {
            l++;
        }
        else
        {
            object temp = a[start_hi];
            for (int k = start_hi - 1; k >= l; k--)
            {
                a[k + 1] = a[k];
                RedrawItem(k + 1);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
            }
            a[l] = temp;
            RedrawItem(l);
            pnlSamples.Refresh();
            if (chkCreateAnimation.Checked)
                SavePicture();
            l++;
            end_lo++;
            start_hi++;
        }
    }
    return a;
}