12,395,378 members (79,800 online)
alternative version

40.7K views
16 bookmarked
Posted

# Merge Sort

, 3 Sep 2009 CPOL
 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
 I much prefer the non-recursive version. I would suggest using one extra array of the same size as the array to be sorted, and having each pass of the sort move data between the two arrays (swap array pointers between passes). That would avoid all but at most one array-copy operation (if there were an odd number of passes, it would be necessary to copy data back to the original array) and would also minimize memory allocation. I did actually just write a non-recursive merge sort routine recently for an embedded processor operating on data stored in flash. Since the particular flash chip I was using greatly favors sequential writes but offers good performance with random reads, merge sort worked out pretty well (sorting 5,000 records in about 20 seconds, in a processor with 3.5K RAM). A four-way merge might be better, but the 5,000-item sort is a worst-case situation so 20 seconds is probably fine).
 Re: Merge sort is a good sort but... Ronnen Nagal3-Sep-09 18:45 Ronnen Nagal 3-Sep-09 18:45
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Jul-16 18:00 Refresh 1