Hello There, Guest!
View New Posts  |  View Today's Posts
[C#] Merge Sort Algorithm Implementation

  • 0 Vote(s) - 0 Average


02-11-2013, 08:16 AM #1
AceInfinity
Developer
*******
Administrators
Posts: 9,733 Threads:1,026 Joined: Jun 2011 Reputation: 76

Merge Sort Algorithm Implementation
Embedded within this class i've added a formula based function which calculates the maximum number of inversions possible, which is based off of n, indicating the array's total number of elements.

The MergeSort has been around for years, and it's still not a bad algorithm, for it's simplicity. The implementation here is a recursive call, because this is a a divide and conquer algorithm. We can break chunks into smaller chunks each recursive call, and compare these smaller subsets of the original object to return elements in a sorted order. If you trace along the steps of this algorithm, it actually ends up looking like a binary tree, because each sequence of elements from the original array during the recursive process is broken up into two individual sequences of elements to be soon compared with one another for determining an order of these elements.

Note: I added an inversion counting method as well, I didn't want to add a boolean directly in the method, because with an algorithm like this, you don' want to slow that recursive call down with anything, so i've kept it out, and provided two methods, which get called depending on what the public method arguments are assigned for when the user calls Sort().

Class:
Code:
namespace SortingUtilities
{
    class MergeSort
    {
        #region Properties
        /// <summary>
        /// Keeps track of the number of inversions for the sorting operation.
        /// </summary>
        private long _inversions = 0;
        public long Inversions
        {
            get
            {
                return _inversions;
            }
        }
        #endregion

        public long[] Sort(long[] array, bool countInversions)
        {
            if (countInversions)
            {
                return InversionCountSort(array);
            }
            else
            {
                return NoCountSort(array);
            }
        }

        #region Sort Methods
        /// <summary>
        /// Sorts an input array of type long recursively using the Merge Sorting
        /// algorithm approach. Also keeps track of the number of inversions performed
        /// for completely sorting the input array.
        /// </summary>
        /// <param name="branch">The current branch in the recursive tree of split elements.</param>
        /// <returns>The sorted elements.</returns>
        private long[] NoCountSort(long[] branch)
        {
            // We split an array branch of 2 elements and there's nothing
            // to sort because we only have one value in this recursive call.
            if (branch.LongLength == 1)
            {
                return branch;
            }

            // Divide the current branch of elements by 2.
            // This will be used as the number of elements for the first
            // array half.
            long lowerSet = branch.LongLength / 2;

            // Create first range of elements from the branch.
            long[] A = new long[lowerSet];
            for (long k = 0; k < A.LongLength; k++)
            {
                A[k] = branch[k];
            }

            // Create last range of elements from the branch.
            long[] B = new long[branch.LongLength - lowerSet];
            for (long k = 0; k < B.LongLength; k++)
            {
                B[k] = branch[k + lowerSet];
            }

            // Sorted array.
            long[] sorted = new long[branch.LongLength];

            // Recursively pass along each split branch to this method.
            A = NoCountSort(A);
            B = NoCountSort(B);

            // i is the left half, j is the right half.
            long i = 0, j = 0;

            // Use i and j for the comparison of the indexed elements for
            // the split array elements to decide a new sort order to place
            // in the sorted array.
            for (long n = 0; n < branch.LongLength; n++)
            {
                if (i == A.LongLength)
                {
                    // We've already exhausted the left half.
                    // Give current index in sorted array to the next value for the right half.
                    sorted[n] = B[j++];
                }
                else if (j == B.LongLength)
                {
                    // We've already exhausted the right half.
                    // Give current index in sorted array to the next value for the left half.
                    sorted[n] = A[i++];
                }
                else
                {
                    sorted[n] = A[i] <= B[j] ? A[i++] : B[j++];
                }
            }
            return sorted;
        }

        /// <summary>
        /// Sort method with inversion count.
        /// </summary>
        /// <param name="branch">The current branch in the recursive tree of split elements.</param>
        /// <returns>The sorted elements.</returns>
        private long[] InversionCountSort(long[] branch)
        {
            if (branch.LongLength == 1)
            {
                return branch;
            }

            long lowerSet = branch.LongLength / 2;

            long[] A = new long[lowerSet];
            for (long k = 0; k < A.LongLength; k++)
            {
                A[k] = branch[k];
            }

            long[] B = new long[branch.LongLength - lowerSet];
            for (long k = 0; k < B.LongLength; k++)
            {
                B[k] = branch[k + lowerSet];
            }

            long[] sorted = new long[branch.LongLength];

            A = InversionCountSort(A);
            B = InversionCountSort(B);

            int i = 0, j = 0;
            for (long n = 0; n < branch.LongLength; n++)
            {
                if (i == A.LongLength)
                {
                    sorted[n] = B[j++];
                }
                else if (j == B.LongLength)
                {
                    sorted[n] = A[i++];
                }
                else if (A[i] <= B[j])
                {
                    sorted[n] = A[i++];
                }
                else
                {
                    sorted[n] = B[j++];
                    _inversions += A.LongLength - i;
                }
            }
            return sorted;
        }
        #endregion

        #region Other Methods
        /// <summary>
        /// Calculate max number of inversions for a specific array length.
        /// Manually calculating this would be the equivilant of a descending
        /// sorted order of the array, when trying to sort in ascending order
        /// or the reverse.
        /// </summary>
        /// <param name="n">Length of the array.</param>
        /// <returns>Maximum number of inversions possible.</returns>
        public static long MaxNumInversions(long n)
        {
            return (n * (n - 1)) / 2;
        }

        /// <summary>
        /// Method that needs to be called in order to reset the inversions count
        /// back to 0 if you don't want a running sum.
        /// </summary>
        public void ResetInversions()
        {
            _inversions = 0;
        }
        #endregion
    }
}

Implementation:
Code:
static void MainMethod()
{
    long[] arr = { 8, 5, 3, 2, 1, 7, 6, 4 };
    MergeSort mergeSort = new MergeSort();
    Console.WriteLine("Array length: {0}", arr.Length);
    Console.WriteLine("Max # inversions possible: {0}", MergeSort.MaxNumInversions(arr.LongLength));
    Console.WriteLine("Not sorted: {0}", string.Join(", ", arr));
    Console.WriteLine("Sorted: {0}", string.Join(", ", mergeSort.Sort(arr, true)));
    Console.WriteLine("Calculated inversions: {0}", mergeSort.Inversions);
    mergeSort.ResetInversions();
}

Basically the Merge Sort algorithm works like this:


We break the initial sequence of elements into parts, sort, then start the merging process by comparing starting from the initial index from each sequence being compared for the joining, in left to right population order.

The asymptotic running time of this algorithm can be compared directly to n * Log⁡(n), where n equals the number of elements in the array.

Test Result:


cheers
This post was last modified: 04-26-2015, 12:36 PM by AceInfinity.


Microsoft MVP .NET Programming - (2012 - Present)
®Crestron DMC-T Certified Automation Programmer

Development Site: aceinfinity.net

 ▲
 ▲ ▲

02-11-2013, 08:25 AM #2
Null
Moderator
*****
Moderators
Posts: 130 Threads:23 Joined: Feb 2012 Reputation: 4

RE: Merge Sort Algorithm Implementation
Cool. I've not studied the Merge Sort yet, only Quick, Bubble, Insertion and Heap. I started writing a class library just for fun really. 


Code:
public sealed class InsertionSort<T> : ISorter<T>
{
    public IEnumerable<T> Sort(IList<T> source)
    {
        return Sort(source, Comparer<T>.Default);
    }

    public IEnumerable<T> Sort(IList<T> source, IComparer<T> comparer)
    {
        for (int i = 1; i < source.Count; i++)
        {
            T value = source[i];
            int index = i - 1;

            while (index >= 0 && comparer.Compare(source[index], value) > 0)
            {
                source[index + 1] = source[index];
                index--;
            }
            source[index + 1] = value;
        }
        return source;
    }
}








This post was last modified: 02-11-2013, 08:26 AM by Null.

02-11-2013, 08:29 AM #3
AceInfinity
Developer
*******
Administrators
Posts: 9,733 Threads:1,026 Joined: Jun 2011 Reputation: 76

RE: Merge Sort Algorithm Implementation
Note: I have tried the Buffer.BlockCopy method, but looping via for loops and assigning based on index seemed slightly faster. I took a look at how the .NET Array methods worked out of curiosity and from first glance it did not appear that they decided to use the Merge Sort algorithm, although, this algorithm is a standard for many sorting methods in other language libraries. What .NET uses is called the introspective sort (named IntroSort()) algorithm. This is a combination of other common algorithms used for sorting, because each comes with their drawbacks and advantages. It starts off with the QuickSort method, which I believe uses a pivot point in the array to sort left and right boundaries, and later moves to the HeapSort algorithm when the recursion depth is fairly branched off, but for smaller cases uses the Insertion sorting algorithm.

edit: Quick reply ByteBlast lol. I'd suggest learning to implement the IntroSort algorithm then if you know those other ones.

cheers
This post was last modified: 02-11-2013, 08:33 AM by AceInfinity.


Microsoft MVP .NET Programming - (2012 - Present)
®Crestron DMC-T Certified Automation Programmer

Development Site: aceinfinity.net

 ▲
 ▲ ▲

02-11-2013, 09:17 AM #4
xyv123
Member
**
Posts: 61 Threads:11 Joined: Jan 2013 Reputation: 4

RE: Merge Sort Algorithm Implementation
Very nice implementation, Ace.
Regarding the usage of merge sort and introsort in libraries:
Merge sort is very useful because is a stable sorting algorithm guaranteeing n*log(n) worst case complexity. Because of this, many libraries use merge sort for providing a stable sort algorithm (for example, most C++ STL implementations use it for stable_sort()).
Also, many libraries implements unstable sorting as introsort (most implementations of STL use it for sort()).
Bubble sort has no value in practice, because one should prefer insertion sort for sorting small arrays.
This post was last modified: 02-11-2013, 09:18 AM by xyv123.

02-11-2013, 09:22 AM #5
AceInfinity
Developer
*******
Administrators
Posts: 9,733 Threads:1,026 Joined: Jun 2011 Reputation: 76

RE: Merge Sort Algorithm Implementation
(02-11-2013, 09:17 AM)xyv123 Wrote:  Very nice implementation, Ace.
Regarding the usage of merge sort and introsort in libraries:
Merge sort is very useful because is a stable sorting algorithm guaranteeing n*log(n) worst case complexity. Because of this, many libraries use merge sort for providing a stable sort algorithm (for example, most C++ STL implementations use it for stable_sort()).
Also, many libraries implements unstable sorting as introsort (most implementations of STL use it for sort()).
Bubble sort has no value in practice, because one should prefer insertion sort for sorting small arrays.

Quote:Bubble sort has no value in practice, because one should prefer insertion sort for sorting small arrays.

I would agree with this.

I knew the Merge Sort algorithm was used as a common or popular standard for lots of libraries out there, but I like the simplicity behind it. Thanks for the feedback !

Thumbs Up

edit: Here is an interative way I found for calculating the number of inversions, this is very slow however, but still accurate:
[code=csharp]static long CalcInversions(int[] array)
{
long counter = 0;
int n = array.Length;

for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (array[i] > array[j])
{
counter++;
}
}
}
return counter;
}[/code]
This post was last modified: 02-11-2013, 09:24 AM by AceInfinity.


Microsoft MVP .NET Programming - (2012 - Present)
®Crestron DMC-T Certified Automation Programmer

Development Site: aceinfinity.net

 ▲
 ▲ ▲

10-11-2013, 08:59 PM #6
AceInfinity
Developer
*******
Administrators
Posts: 9,733 Threads:1,026 Joined: Jun 2011 Reputation: 76

RE: Merge Sort Algorithm Implementation
Beefed this one up a bit:
[code=csharp]namespace SortingUtilities
{
class MergeSort<TElement> where TElement : IComparable<TElement>, new()
{
#region Properties

public MergeSort()
{
Inversions = 0;
}

public long Inversions { get; private set; }

#endregion

public TElement[] Sort(TElement[] collection, bool countInversions)
{
return countInversions ? InversionCountSort(collection) : NoCountSort(collection);
}

#region Sort Methods
/// <summary>
/// Sorts an input array of type long recursively using the Merge Sorting
/// algorithm approach. Also keeps track of the number of inversions performed
/// for completely sorting the input array.
/// </summary>
/// <param name="branch">The current branch in the recursive tree of split elements.</param>
/// <returns>The sorted elements.</returns>
private static TElement[] NoCountSort(TElement[] branch)
{
// We split an array branch of 2 elements and there's nothing
// to sort because we only have one value in this recursive call.
if (branch.Length == 1) return branch;

// Divide the current branch of elements by 2.
// This will be used as the number of elements for the first
// array half.
int lowerSet = branch.Length / 2;

// Create first range of elements from the branch.
TElement[] A = new TElement[lowerSet];
for (int k = 0; k < A.Length; k++) A[k] = branch[k];

// Create last range of elements from the branch.
TElement[] B = new TElement[branch.Length - lowerSet];
for (int k = 0; k < B.Length; k++) B[k] = branch[k + lowerSet];

// Sorted array.
TElement[] sorted = new TElement[branch.Length];

// Recursively pass along each split branch to this method.
A = NoCountSort(A);
B = NoCountSort(B);

// i is the left half, j is the right half.
int i = 0, j = 0;

// Use i and j for the comparison of the indexed elements for
// the split array elements to decide a new sort order to place
// in the sorted array.
for (int n = 0; n < branch.Length; n++)
{
if (i == A.Length)
{
// We've already exhausted the left half.
// Give current index in sorted array to the next value for the right half.
sorted[n] = B[j++];
}
else if (j == B.Length)
{
// We've already exhausted the right half.
// Give current index in sorted array to the next value for the left half.
sorted[n] = A[i++];
}
else
{
sorted[n] = A[i].CompareTo(B[j]) < 1 ? A[i++] : B[j++];
}
}
return sorted;
}

/// <summary>
/// Sort method with inversion count.
/// </summary>
/// <param name="branch">The current branch in the recursive tree of split elements.</param>
/// <returns>The sorted elements.</returns>
private TElement[] InversionCountSort(TElement[] branch)
{
if (branch.Length == 1) return branch;

int lowerSet = branch.Length / 2;

TElement[] A = new TElement[lowerSet];
for (int k = 0; k < A.Length; k++) A[k] = branch[k];

TElement[] B = new TElement[branch.Length - lowerSet];
for (int k = 0; k < B.Length; k++) B[k] = branch[k + lowerSet];

TElement[] sorted = new TElement[branch.Length];

A = InversionCountSort(A);
B = InversionCountSort(B);

int i = 0, j = 0;
for (int n = 0; n < branch.Length; n++)
{
if (i == A.Length) sorted[n] = B[j++];
else if (j == B.Length) sorted[n] = A[i++];
else if (A[i].CompareTo(B[j]) < 1) sorted[n] = A[i++];
else
{
sorted[n] = B[j++];
Inversions += A.Length - i;
}
}
return sorted;
}
#endregion

#region Other Methods
/// <summary>
/// Calculate max number of inversions for a specific array length.
/// Manually calculating this would be the equivalent of a descending
/// sorted order of the array, when trying to sort in ascending order
/// or the reverse.
/// </summary>
/// <param name="n">Length of the array.</param>
/// <returns>Maximum number of inversions possible.</returns>
public static long MaxNumInversions(long n)
{
return (n * (n - 1)) / 2;
}

/// <summary>
/// Method that needs to be called in order to reset the inversions count
/// back to 0 if you don't want a running sum.
/// </summary>
public void ResetInversions()
{
Inversions = 0;
}
#endregion
}
}[/code]

Now we're using simple generics.
This post was last modified: 10-11-2013, 09:00 PM by AceInfinity.


Microsoft MVP .NET Programming - (2012 - Present)
®Crestron DMC-T Certified Automation Programmer

Development Site: aceinfinity.net

 ▲
 ▲ ▲




Forum Jump:


Possibly Related Threads...
Thread Author Replies Views Last Post
   Basic Generic Publisher/Subscriber Implementation AceInfinity 0 501 11-19-2017, 01:56 AM
Last Post: AceInfinity
   Simple PriorityQueue<T> Implementation AceInfinity 0 206 11-19-2017, 01:50 AM
Last Post: AceInfinity
  Shunting Yard algorithm for logical expressions kerplunk 2 3,858 02-25-2013, 07:56 AM
Last Post: Morpheus
Information  Sort Values From An Input Array (Determined Integer Array or String Array VALUES) AceInfinity 2 2,113 03-26-2012, 05:14 PM
Last Post: AceInfinity
  FBytes - Binary Merge Tool AceInfinity 10 9,380 01-04-2012, 05:32 PM
Last Post: AceInfinity


Users browsing this thread: 1 Guest(s)