Merge Sort

Merge-sort is an application of Divide and Conquer paradigm. To read more about Divide and Conquer, follow this post. 

In merge-sort we follow following steps:
1. Divide the original array of size n into 2 halves of size n/2 each
2. Sort the two halves individually.
3. Merge the two sorted halves to get a sorted array of original size.

Following is the C++ implementation of merge sort , for an unsorted array of integers : {6, 2, 8, 12, 10, 9, 50, 24, 3, 1}


#include <iostream>
using namespace std;

#define MAX_NUM 100

// Auxiliary function to merge 2 sorted sub-arrays and produce a sorted array
void merge(int arr1[], int low, int pivot, int high)
{
    int arr2[MAX_NUM];

    cout << "Merging arrays : [ " ;
    for(int x=low; x<=pivot; x++)
        cout << arr1[x] << " ";
    cout << "] and [ ";
    for(int x=pivot+1; x<=high; x++)
        cout << arr1[x] << " ";
    cout << "]" << endl;

    int count = high-low;

    int mid = pivot+1;
    int i = low;
    while(low <= pivot && mid <= high)
    {
        if(arr1[low] <= arr1[mid])
            arr2[i++] = arr1[low++];
        else
            arr2[i++] = arr1[mid++];
    }
    while(mid <= high)
        arr2[i++] = arr1[mid++];

    while(low <= pivot)
        arr2[i++] = arr1[low++];

    cout << "Merged Array: [ ";

    // Copy sorted values from arr2 to original array arr1
    for(int x=0; x<=count; x++)
    {
        cout << arr2[high-count+x] << "  ";
        arr1[high-count+x] = arr2[high-count+x];
    }
    cout << "]" << endl;
}

// Main mergeSort function
void mergeSort(int arr1[], int low, int high)
{
    cout << "Merge sort called on array : [ " ;
    for(int x=low; x<=high; x++)
        cout << arr1[x] << " ";
    cout << "]" << endl;

    if(low < high)
    {
        int mid = (high+low)/2;
        mergeSort(arr1, low, mid);
        mergeSort(arr1, mid+1, high);
        merge(arr1, low, mid, high);
    }
}

// an auxiliary function to print the contents of an array
void printArray(int arr[], int n){
    cout << "{ ";
    for(int i=0; i<n; i++)
        cout << arr[i] << "  ";
    cout << "}" << endl;
}

int main(int argc, char* argv[])
{
    int A[10] = {6, 2, 8, 12, 10, 9, 50, 24, 3, 1};
    cout << "Original Array : ";    printArray(A, 10);

    mergeSort(A, 0, 9);
    cout << "Sorted Array : ";    printArray(A, 10);

    return 0;
}

Output :

Original Array : { 6  2  8  12  10  9  50  24  3  1  }
Merge sort called on array : [ 6 2 8 12 10 9 50 24 3 1 ]
Merge sort called on array : [ 6 2 8 12 10 ]
Merge sort called on array : [ 6 2 8 ]
Merge sort called on array : [ 6 2 ]
Merge sort called on array : [ 6 ]
Merge sort called on array : [ 2 ]
Merging arrays : [ 6 ] and [ 2 ]
Merged Array: [ 2  6  ]
Merge sort called on array : [ 8 ]
Merging arrays : [ 2 6 ] and [ 8 ]
Merged Array: [ 2  6  8  ]
Merge sort called on array : [ 12 10 ]
Merge sort called on array : [ 12 ]
Merge sort called on array : [ 10 ]
Merging arrays : [ 12 ] and [ 10 ]
Merged Array: [ 10  12  ]
Merging arrays : [ 2 6 8 ] and [ 10 12 ]
Merged Array: [ 2  6  8  10  12  ]
Merge sort called on array : [ 9 50 24 3 1 ]
Merge sort called on array : [ 9 50 24 ]
Merge sort called on array : [ 9 50 ]
Merge sort called on array : [ 9 ]
Merge sort called on array : [ 50 ]
Merging arrays : [ 9 ] and [ 50 ]
Merged Array: [ 9  50  ]
Merge sort called on array : [ 24 ]
Merging arrays : [ 9 50 ] and [ 24 ]
Merged Array: [ 9  24  50  ]
Merge sort called on array : [ 3 1 ]
Merge sort called on array : [ 3 ]
Merge sort called on array : [ 1 ]
Merging arrays : [ 3 ] and [ 1 ]
Merged Array: [ 1  3  ]
Merging arrays : [ 9 24 50 ] and [ 1 3 ]
Merged Array: [ 1  3  9  24  50  ]
Merging arrays : [ 2 6 8 10 12 ] and [ 1 3 9 24 50 ]
Merged Array: [ 1  2  3  6  8  9  10  12  24  50  ]
Sorted Array : { 1  2  3  6  8  9  10  12  24  50  }

Divide and Conquer - Concepts and Applications

In divide-and-conquer, we solve a problem recursively, applying three steps at each level of the recursion:

1. Divide the problem into a number of sub-problems that are smaller instances of the same problem.
2. Conquer the sub-problems by solving them recursively. If the sub-problem sizes are small enough, however, just solve the sub-problems in a straightforward manner.
3. Combine the solutions to the sub-problems into the solution for the original problem.

                                          Source : http://faculty.simpson.edu/

When the sub-problems are large enough to solve recursively, we call that the recursive case. Once the sub-problems become small enough that we no longer recurse, we say that the recursion “bottoms out” and that we have gotten down to the base case.

Applications of Divide and Conquer:

1. Merge Sort
2. Maximum sub-array problem
3. Matrix multiplication
4. Finding closest pair(points) in 2D-plane
5. Integer multiplication
6. Quick Sort
7. Binary Search

Performance Analysis:

For Divide-and-Conquer algorithms the running time is mainly affected by 3 criteria:

The number of sub-instances (alpha) into which a problem is split.
The ratio of initial problem size to sub-problem size. (beta)
The number of steps required to divide the initial instance and to combine sub-solutions, expressed as a function of the input size, n.
Suppose, P, is a divide-and-conquer algorithm that instantiates alpha sub-instances, each of size n/beta.

Let Tp( n ) denote the number of steps taken by P on instances of size n. Then

Tp( n0 )  =  Constant   (Recursive-base)
Tp( n )   =  alpha Tp( n/beta ) + gamma( n )

In the case when alpha and beta are both constant (as in all the examples we have given) there is a general method that can be used to solve such recurrence relations in order to obtain an asymptotic bound for the running time Tp( n ).

In general:

T( n )  =  alpha T( n/beta ) + O( n^gamma )
(where gamma is constant) has the solution


                  O(n^gamma)             if   alpha < beta^gamma
T( n )  =    O(n^gamma log n)       if   alpha = beta^gamma}
                  O(n^{log^-beta(alpha)) if   alpha > beta^gamma

Advantages:

1. Solving difficult problems:
Divide and conquer is a powerful tool for solving conceptually difficult problems: all it requires is a way of breaking the problem into sub-problems, of solving the trivial cases and of combining sub-problems to the original problem.

2. Parallelism:
Divide and conquer algorithms are naturally adapted for execution in multi-processor machines, especially shared-memory systems where the communication of data between processors does not need to be planned in advance, because distinct sub-problems can be executed on different processors.

3. Memory Access:
Divide-and-conquer algorithms naturally tend to make efficient use of memory caches. The reason is that once a sub-problem is small enough, it and all its sub-problems can, in principle, be solved within the cache, without accessing the slower main memory. 

4. Roundoff control:
In computations with rounded arithmetic, e.g. with floating point numbers, a divide-and-conquer algorithm may yield more accurate results than a superficially equivalent iterative method.


References:
http://en.wikipedia.org/wiki/Divide_and_conquer_algorithms
http://www.amazon.com/Introduction-Algorithms-Edition-Thomas-Cormen/dp/0262033844
http://cgi.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html

Divide and Conquer

Merge sort - Divide & Conquer
Merge-sort is an application of Divide and Conquer paradigm. To read more about Divide and Conquer, follow this post. 
In merge-sort we follow following steps:
Read more...

---

Divide and conquer - concepts & applications
In divide-and-conquer, we solve a problem recursively, applying three steps at each level of the recursion: 
1.Divide the problem into a number of sub-problems that are smaller instances of the same problem.
Read more...

---