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
}
}
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();
}
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;
}
}
(02112013, 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.
Possibly Related Threads...  
Thread  Author  Replies  Views  Last Post  
Basic Generic Publisher/Subscriber Implementation  AceInfinity  0  179 
11192017, 01:56 AM Last Post: AceInfinity 

Simple PriorityQueue<T> Implementation  AceInfinity  0  35 
11192017, 01:50 AM Last Post: AceInfinity 

Shunting Yard algorithm for logical expressions  kerplunk  2  3,385 
02252013, 07:56 AM Last Post: Morpheus 

Sort Values From An Input Array (Determined Integer Array or String Array VALUES)  AceInfinity  2  1,861 
03262012, 05:14 PM Last Post: AceInfinity 

FBytes  Binary Merge Tool  AceInfinity  10  7,953 
01042012, 05:32 PM Last Post: AceInfinity 