Click here to Skip to main content
15,029,308 members
Articles / Programming Languages / C#
Posted 3 Sep 2009


16 bookmarked

Merge Sort

Rate me:
Please Sign up or sign in to vote.
4.60/5 (7 votes)
3 Sep 2009CPOL2 min read
Using Merge Sort
Image 1


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.


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,
            // 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;

                // 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;

                                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.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Ronnen Nagal
Canada Canada
No Biography provided

Comments and Discussions

Generalneed more testing ... Pin
oldyellowcat13-Dec-11 22:31
Memberoldyellowcat13-Dec-11 22:31 
GeneralRe: need more testing ... Pin
ostrovitch6-Nov-13 10:42
Memberostrovitch6-Nov-13 10:42 
QuestionGreat Code Pin
michellm5-Oct-11 10:15
Membermichellm5-Oct-11 10:15 
Generalfinding the majority Pin
ronny2215-Nov-09 23:45
Memberronny2215-Nov-09 23:45 
GeneralGreat Work ! Pin
Robert3456-Sep-09 22:39
MemberRobert3456-Sep-09 22:39 
GeneralPretty good Pin
wshcdr3-Sep-09 21:31
Memberwshcdr3-Sep-09 21:31 
GeneralRe: Pretty good Pin
Ronnen Nagal4-Sep-09 1:56
MemberRonnen Nagal4-Sep-09 1:56 
GeneralMerge sort is a good sort but... Pin
supercat93-Sep-09 10:14
Membersupercat93-Sep-09 10:14 
GeneralRe: Merge sort is a good sort but... Pin
Ronnen Nagal3-Sep-09 18:45
MemberRonnen Nagal3-Sep-09 18:45 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.