Friday, June 17, 2011

What is Merge Sort algorithm? How to implement Merge Sort in C++?

  • Merge Sort  is a divide and conquer algorithm.
  • In the best/ average/ worst case it gives a time complexity of O(n log n).
Conceptually, a merge sort works as follows:
  1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
  2. Divide the unsorted list into two sublists of about half the size.
  3. Sort each sublist recursively by re-applying the merge sort.
  4. Merge the two sublists back into one sorted list.
(Reference: http://en.wikipedia.org/wiki/Merge_sort)

Demonstrate a simple merge sort implementation

#include <iostream>
#include <cmath>
using namespace std;

const int INPUT_SIZE = 10;

// A simple print function
void print(int *input)
{
    for ( int i = 0; i < INPUT_SIZE; i++ )
        cout << input[i] << " ";
    cout << endl;
}

void merge(int* input, int p, int r)
{
    int mid = floor((p + r) / 2);
    int i1 = 0;
    int i2 = p;
    int i3 = mid + 1;

    // Temp array
    int temp[r-p+1];

    // Merge in sorted form the 2 arrays
    while ( i2 <= mid && i3 <= r )
        if ( input[i2] < input[i3] )
            temp[i1++] = input[i2++];
        else
            temp[i1++] = input[i3++];

    // Merge the remaining elements in left array
    while ( i2 <= mid )
        temp[i1++] = input[i2++];

    // Merge the remaining elements in right array
    while ( i3 <= r )
        temp[i1++] = input[i3++];

    // Move from temp array to master array
    for ( int i = p; i <= r; i++ )
        input[i] = temp[i-p];
}

void merge_sort(int* input, int p, int r)
{
    if ( p < r )
    {
        int mid = floor((p + r) / 2);
        merge_sort(input, p, mid);
        merge_sort(input, mid + 1, r);
        merge(input, p, r);
    }
}

int main()
{
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    merge_sort(input, 0, 9);
    cout << "Output: ";
    print(input);
    return 0;
}

OUTPUT:-

Input: 500 700 800 100 300 200 900 400 1000 600
Output: 100 200 300 400 500 600 700 800 900 1000

18 comments :

  1. very clear, self-explanatory and concise

    ReplyDelete
  2. awesome example, very clear

    ReplyDelete
  3. error C2668: 'floor' : ambiguous call to overloaded function

    ReplyDelete
  4. The only thing I don't get is floor.... :\

    ReplyDelete
    Replies
    1. Did anyone get this code to work with this overloaded function "floor" not compiling- 1 error

      Delete
    2. You just need #include "Math.h" for the floor function.

      Delete
  5. Its not necessary to floor it. Replace that particular assignment statement with int mid =((p + r) / 2);

    ReplyDelete
  6. Here is a version without floor: Good luck!
    #include
    #include
    using namespace std;

    const int INPUT_SIZE = 10;

    // A simple print function
    void print(int *input)
    {
    for ( int i = 0; i < INPUT_SIZE; i++ )
    cout << input[i] << " ";
    cout << endl;
    }

    void merge(int* input, int p, int r)
    {
    int mid = ((p + r) / 2);
    int i1 = 0;
    int i2 = p;
    int i3 = mid + 1;

    // Temp array
    int temp[1000];

    // Merge in sorted form the 2 arrays
    while ( i2 <= mid && i3 <= r )
    if ( input[i2] < input[i3] )
    temp[i1++] = input[i2++];
    else
    temp[i1++] = input[i3++];

    // Merge the remaining elements in left array
    while ( i2 <= mid )
    temp[i1++] = input[i2++];

    // Merge the remaining elements in right array
    while ( i3 <= r )
    temp[i1++] = input[i3++];

    // Move from temp array to master array
    for ( int i = p; i <= r; i++ )
    input[i] = temp[i-p];
    }

    void merge_sort(int* input, int p, int r)
    {
    if ( p < r )
    {
    int mid = ((p + r) / 2);
    merge_sort(input, p, mid);
    merge_sort(input, mid + 1, r);
    merge(input, p, r);
    }
    }

    int main()
    {
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600};
    cout << "Input: ";
    print(input);
    merge_sort(input, 0, 9);
    cout << "Output: ";
    print(input);
    system("pause");
    return 0;
    }
    /*OUTPUT:-
    Input: 500 700 800 100 300 200 900 400 1000 600
    Output: 100 200 300 400 500 600 700 800 900 1000*/

    ReplyDelete
  7. really nice code but missing some explanations, if anyone wants step by step explanation then it could be found here http://www.hellgeeks.com/merge-sort/

    ReplyDelete
  8. how could i print the output in its all steps..plz help me

    ReplyDelete

Contact Form

Name

Email *

Message *

Back to Top