Click here to Skip to main content
Click here to Skip to main content

Merge Sort

, 3 Sep 2009
Rate this:
Please Sign up or sign in to vote.
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.

License

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

Share

About the Author

Ronnen Nagal

Israel Israel
No Biography provided

Comments and Discussions

 
Generalneed more testing ... Pinmemberoldyellowcat13-Dec-11 22:31 
GeneralRe: need more testing ... Pinmemberostrovitch6-Nov-13 10:42 
QuestionGreat Code Pinmembermichellm5-Oct-11 10:15 
Generalfinding the majority Pinmemberronny2215-Nov-09 23:45 
GeneralGreat Work ! PinmemberRobert3456-Sep-09 22:39 
GeneralPretty good Pinmemberwshcdr3-Sep-09 21:31 
GeneralRe: Pretty good PinmemberRonnen Nagal4-Sep-09 1:56 
GeneralMerge sort is a good sort but... Pinmembersupercat93-Sep-09 10:14 
GeneralRe: Merge sort is a good sort but... PinmemberRonnen Nagal3-Sep-09 18:45 

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

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

| Advertise | Privacy | Mobile
Web01 | 2.8.140821.2 | Last Updated 3 Sep 2009
Article Copyright 2009 by Ronnen Nagal
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid