11,706,159 members (58,226 online)

# Merge Sort

, 3 Sep 2009 CPOL 37.7K 656 16
 Rate this:
Using Merge Sort

## Introduction

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 short research, I decided to write a Generic Merge-Sort Class that will work for me. During the work, I found a few major points that should be considered while using that Generic Class for Sorting.

## Background

Merge Sort (pseudo-code in the picture) is a recursive algorithm, that splits an array of the objects to 2 sub arrays - A,B (which initialize to infinite values), sorts this into 2 sub-arrays and finally merges them. (Hence, 'merge' sort)

## Using the Code

For using the Generic Merge Sort, you should (probably) know what is the objects parameter by which the objects will be sorted.

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.)

```class MergeSort
{
/// <span class="code-SummaryComment"><summary></span>
/// 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
/// <span class="code-SummaryComment"></summary></span>
/// <span class="code-SummaryComment"><param name="X"></param></span>
public static T[] Merge_Sort<T>(T[] X) where T : IComparable, new()
{
int n = X.Length;
X = MegrgeSort_Internal(X, n);
return X;
}

/// <span class="code-SummaryComment"><summary></span>

/// Internal method for sorting
/// <span class="code-SummaryComment"></summary></span>
/// <span class="code-SummaryComment"><param name="X"></param></span>
/// <span class="code-SummaryComment"><param name="n"></param></span>
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;

} // MegrgeSort_Internal
}```

## Points of Interest

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.

There are two projects attached:

The first one is a simple (int32) Implementation, that sorts an array of integers. The second one is the Generic Merge Sort, Plus a simple 'Person' class that will demonstrate the using of the Generic code.

## Share

 Israel
No Biography provided

## You may also be interested in...

 First Prev Next
 need more testing ... oldyellowcat13-Dec-11 22:31 oldyellowcat 13-Dec-11 22:31
 Re: need more testing ... ostrovitch6-Nov-13 10:42 ostrovitch 6-Nov-13 10:42
 Great Code michellm5-Oct-11 10:15 michellm 5-Oct-11 10:15
 finding the majority ronny2215-Nov-09 23:45 ronny22 15-Nov-09 23:45
 Great Work ! Robert3456-Sep-09 22:39 Robert345 6-Sep-09 22:39
 Pretty good wshcdr3-Sep-09 21:31 wshcdr 3-Sep-09 21:31
 Re: Pretty good Ronnen Nagal4-Sep-09 1:56 Ronnen Nagal 4-Sep-09 1:56
 Merge sort is a good sort but... supercat93-Sep-09 10:14 supercat9 3-Sep-09 10:14
 Re: Merge sort is a good sort but... Ronnen Nagal3-Sep-09 18:45 Ronnen Nagal 3-Sep-09 18:45
 I agree that on a limited-resources environment, a non-recursive routine will perform better. (The stack has Its limitation) But using C# application on Hardware with capabilities, I prefer the recursive implementation with the Stack-Calls. Please notice that Merge-Sort runs on the best running-time - O(nlogn), and that is a major Point to consider.
 Last Visit: 31-Dec-99 18:00     Last Update: 29-Aug-15 23:09 Refresh 1