[C#] Merge Sort Algorithm Implementation

AceInfinity · Feb 11, 2013

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 <= 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 <= 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⁡, where n equals the number of elements in the array.

Test Result:

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.

:thumbsup2:

Search

Search

[C#] Merge Sort Algorithm Implementation

AceInfinity

Emeritus, Contributor