Sorting is a common activity in the programming work.
Merge-Sort is one of the best implementation for Sorting,
Since Its running on O(nlogn) - which is the best run-time available for Sorting.
On one of my projects I had a requirement to sort Objects.
After a short research, I decided to write a Generic Merge-Sort Class that will work for me.
During the work, I found few major points that should be considered while using that Generic Class for Sorting. (publication)

• Preface

Merge Sort (pseudo-code in the picture) is a recursive algorithm, that Split an Array of the Objects to 2 sub Arrays - A,B (which initialize to infinite values), Sort this 2 sub-Arrays and finally merge them. (Therefore, 'merge' sort)

• Using

For using the Generic Merge Sort, you should (probably) know what is the objects parameter that the objects will be sorted by.
Now, Since the 2 sub-Arrays should be initialized with an infinite value, You should use the default-ctor to make that initialization.

• Example

For sorting an Array of 'Persons' Objects that will be sorted according to their ID number (from low to high), you should declare infinite ID-number (infinite int32 value) in the default-ctor.
(I know This is not an elegant implementation, but In that case there is no alternative.)

• Points for attention

When writing a class for using Generic Merge Sort, you should implement the 'IComparable' interface since the code using the 'CompareTo' function - to compare objects.
You should also write your own 'overloading operators' that will be in use to compare objects: ==, !=, >, >=, <, <= plus 'Equals' and 'GetHashCode'. Please notice that 'GetHashCode' will be in use by the CLR implicitly - so you must write your own implementation that will return the same value for the same object.

class MergeSort { /// <summary> /// Sorts an array of Objects /// IComparable - use 'CompareTo' to compare objects /// where T : new() - need to create a new Type 'T' object inside the method /// </summary> /// <param name="X"></param> public static T[] Merge_Sort<T>(T[] X) where T : IComparable, new() { int n = X.Length; X = MegrgeSort_Internal(X, n); return X; } /// <summary> /// Internal method for sorting /// </summary> /// <param name="X"></param> /// <param name="n"></param> private static T[] MegrgeSort_Internal<T>(T[] X, int n) where T : IComparable, new() { // Define 2 aid Sub-Arrays T[] A = new T[(n / 2) + 2]; T[] B = new T[(n / 2) + 2]; // Initialize the 2 Sub-Arrays with an infinite 'sorting parameter' // Therefor, You must include a default ctor in your class // which will initialize an infinite value - To the sorting parameter // using 'where T : new()' here for (int i = 0; i < A.Length; i++) { A[i] = new T(); ; B[i] = new T(); } // Recursive Stop-Condition, Sorting a Basic Array (Size 2) if (n == 2) { int CompareValue = X[0].CompareTo(X[1]); if (CompareValue > 0) { T tempT = X[0]; X[0] = X[1]; X[1] = tempT; } } else { // The Sub-Arrays Size is Large than 2 if (n > 2) { int m = n / 2; // Initialize the 2 Sub-Arrays (The first relevant values) for (int i = 0; i < m; i = i + 1) { A[i] = X[i]; } for (int j = m; j < n; j++) { B[j - m] = X[j]; } // 2 Recursive Calling, Sorting Sub-Arrays A = MegrgeSort_Internal(A, m); B = MegrgeSort_Internal(B, n - m); // Merging the Sorted Sub-Arrays into the main Array int p = 0; int q = 0; for (int k = 0; k < n; k++) { { int CompareValure = A[p].CompareTo(B[q]); if (CompareValure == 0 || CompareValure == -1) { X[k] = A[p]; p = p + 1; } else { X[k] = B[q]; q = q + 1; } } } } // if } // else return X; } }

2 project attached:

• A simple (int32) Implementation, that Sorts an Array of Integers
• A Generic Merge Sort, Plus a simple 'Person' class that will demonstrate the using of the Generic code

Simple Merge Sort Download
Generic Merge Sort Download