Merge Sort

The divide-and-conquer approach

Many useful algorithms are recursive in structure: to solve a given problem, they call themselves recursively one or more times to deal with closely related subproblems. These algorithms typically follow a divide-and-conquer approach: they break the problem into several subproblems that are similar to the original problem but smaller in size, solve the subproblems recursively, and then combine these solutions to create a solution to the original problem. The divide-and-conquer paradigm involves three steps at each level of the recursion:
Divide the problem into a number of subproblems that are smaller instances of the same problem.

Conquer the subproblems by solving them recursively. If the subproblem sizes are
small enough, however, just solve the subproblems in a straightforward manner.

Combine the solutions to the subproblems into the solution for the original problem.

In Merge Sort

The merge sort algorithm closely follows the divide-and-conquer paradigm. ntuitively, it operates as follows.
Divide : Divide the n-element sequence to be sorted into two subsequences of n=2 elements each.
Conquer : Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.

The recursion “bottoms out” when the sequence to be sorted has length 1, in which case there is no work to be done, since every sequence of length 1 is already in sorted order.

Psudo Code

MERGE-SORT( A , p , r )
1   IF p < r
2   q ← ⌊ ( p + r ) / 2 ⌋
3 MERGE-SORT( A , p , q )
4 MERGE-SORT( A , q + 1 , r )
5 MERGE( A , p , q , r )
............................................................................

  MERGE(A, p, q, r)
  1   n1← q -p + 1
  2   n2← r -q
  3 //create arrays L[1………n1 + 1 ] and R[ 1. . . . n2 + 1 ]
  4   for i ← 1 to n1
  5         L[ i ] ← A[ p + i -1]
  6         for j ← 1 to n2
  7             R[ j ] ← A[ q + j ]
  8         L[ n1+ 1 ] ← ∞
  9       R[ n2+ 1 ] ← ∞
  10       i ← 1
  11       j ← 1
  12         for k ← p to r
  13           if L[ i ] ≤ R[ j ]
  14                 A[ k ] ← L[ i ]
  15                   i ← i + 1
  16.           else
  17               A[ k ] ← R[ j ]
  18               j ← j + 1

In detail, the MERGE procedure works as follows. Line 1 computes the length n1 of the subarray A[p .. q], and line 2 computes the length n2 of the subarray A[q+1.. r]. We create arrays L and R (“left” and “right”), of lengths n1 C 1 and n2 C 1, respectively, in line 3; the extra position in each array will hold the sentinel. The for loop of lines 4–5 copies the subarray A[p .. q] into L[1.. n1], and the for loop of lines 6–7 copies the subarray A[ q + 1 ...r] into R[1... n2]. Lines 8–9 put the sentinels at the ends of the arrays L and R.

At the start of each iteration of the for loop of lines 12–17, the subarray A[p ... k- 1] contains the k p smallest elements of L[1... n1+ 1] and R[1 ... n2 + 1], in sorted order. Moreover, L[i ]and R[j] are the smallest elements of their arrays that have not been copied back into A.

Merge Sort Implement in C

1 void merge ( int a[ ] , int low , int mid , int high ) {
2   int b[ 10000 ] ;
3   int i = low , j = mid + 1, k = 0 ;
4     while ( i <= mid && j <= high ) {
5     if ( a[ i ] <= a[ j ] )
6         b[ k++ ] = a[ i++ ] ;
7     else
8          b[ k++ ] = a[ j++ ] ;
9     }
10 while ( i <= mid ) {
11           b[ k++ ] = a[ i++ ] ;
12       while ( j <= high)
13           b[ k++ ] = a[ j++ ] ;
14           k - - ; }

15 while ( k >= 0 ) {
16        a[ low + k ] = b[ k ] ;
17        k - - ;
18      }
19 }

20   void mergesort ( int a[ ] , int low , int high ) {
21       if ( low < high ) {
22           int m = ( high + low ) / 2 ;
23           mergesort( a , low , m ) ;
24           mergesort( a , m + 1 , high ) ;
25           merge( a , low , m , high ) ;
26     }
2v   }

Merge sort implement in C++

1   #include <iostream>
2   #include <cstdlib>
3   #include <time.h>

4   using namespace std;
5   const unsigned long long infinity = NULL;

//funtions merge sort

6   void merge ( int* A , int p , const int q , const int r ) {

7       const int n_1 = q - p + 1 ; //lenght size of left side of array.
8       const int n_2 = r - q ; // lenght size of right side of array.
9       int* L = new int [ n_1 + 1 ] ; // declarign the arrays
10       int* R = new int [ n_2 + 1 ] ;
// implementing infinity to last elements of the arrays
11       L[ n_1 ] = infinity;
12       R[ n_2 ] = infinity; // put array element in to the these arrays
13       for( int i = 0 ; i < n_1 ; i++ ) {
14       L[ i ] = A [ p + i ] ; }
15       for (int j = 0 ; j < n_2 ; j++ ) {
16           R[ j ] = A [ q + j + 1 ] ;
            int i = 0 ; }
17       int j = 0 ; //comaring the two arrays and merge the arrays
18       int k ;
19       for ( k = p ; k <= r && i < n_1 && j < n_2 ; ++k )
20       {   if ( L[ i ] <= R[ j ] )
21           {   A[ k ] = L[ i ] ;
22              i ++ ;
23           }
24           else
25           {   A[ k ] = R[ j ] ;
26              j ++;
27.          }
28       } // Added the following two loop.
29   // Note only zero or one loop will actually activate.
30       while ( i < n_1 ) {

A[ k++ ] = L[ i++ ] ;
31 while ( j < n_2) {

A[ k++ ] = R[ j++ ] ;
32      }
33   }

33   void merge_sort( int* A , const int p , const int r ) {
34       if ( p < r )
35       {   int q = ( p + r ) / 2 ;
36          merge_sort( A , p , q ) ;
37          merge_sort( A , q+1 , r ) ;
38          merge( A , p , q , r ) ;
39       }
40   }

41   int main( ) {
42        int length = 10 ;
43      int A[ length ] ; //randomly creating array and print the Array
44       for( int i = 0 ; i < length ; i++ ) {
45        A[ i ] = rand( ) %99 - 1 ; // randow numbers between 1 and 99.
46            cout << A[ i ] << " " ;
47       }
48.       merge_sort( A , 0 , length - 1 ) ;
49       return 0 ;
50   }

__________________________________________________________________________________________

Merge sort implement in Java

1   package cse_helper;

2   public class MergeSort {

3       private int[ ] array;
4       private int[ ] tempMergArr;
5       private int length;

6         public static void main( String a[ ] ) {

7             int[ ] inputArr = { 45 , 23 ,11, 89 , 77 , 98 , 4 , 28 , 65 , 43 } ;
8             System.out.print( "input array \n " ) ;
9             for ( int i : inputArr ) {
10               System.out.print( i ) ;
11               System.out.print( " " ) ;
12   }
13   MergeSort mms = new MergeSort( ) ;
14                mms.sort( inputArr ) ;
15              System.out.print ( "\n output array \n " ) ;
16            for ( int i : inputArr ) {
17      System.out.print ( i ) ;
18   System.out.print ( " " ) ;
19   }
20       }

21       public void sort ( int inputArr[ ] ) {
22      this.array = inputArr ;
23      this.length = inputArr.length ;
24      this.tempMergArr = new int [ length ] ;
25      MergeSort ( 0 , length - 1 ) ;
26 }

27       private void MergeSort ( int lowerIndex , int higherIndex ) {
28             if ( lowerIndex < higherIndex ) {
29              int middle = lowerIndex + ( higherIndex - lowerIndex ) / 2 ;
30          MergeSort ( lowerIndex , middle ) ;
31          MergeSort( middle + 1 , higherIndex ) ;
32          merge( lowerIndex , middle , higherIndex ) ;
33      }
34           }

35       private void merge( int lowerIndex , int middle , int higherIndex ) {
36        for ( int i = lowerIndex ; i <= higherIndex ; i++ ) {
37           tempMergArr[ i ] = array[ i ] ;
38         }
39      int i = lowerIndex;
40      int j = middle + 1;
41      int k = lowerIndex;
42      while ( i <= middle && j <= higherIndex ) {
43        if ( tempMergArr[ i ] <= tempMergArr[ j ] ) {
44              array[ k ] = tempMergArr[ i ] ;
45              i++;
46            } else {
47              array[ k ] = tempMergArr[ j ] ;
48              j++;
49           }
50            k++;
51       }
52        while (i <= middle) {
53            array[ k ] = tempMergArr[ i ] ;
54            k++;
55             i++;
56        }
57   }
58   }

CSE Helper