Merge sort in cpp

C++ Program to Implement Merge Sort

Merge sort in C++ is defined as a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.

The divide and concur have the following three tasks.

1. Divide the problems into subproblems similar to the original but smaller in size.
2. Conquer the sub-problems recursively. If they are smaller in size, straightforwardly solve them.
3. Combine those solutions into a solution, the answer to the original problem.

Let’s understand the merge sort in C++ and then write a program demonstrating it.

How the “divide and conquer” Algorithm works in Merge Sort

Sorting Problem: Sort a sequence of n elements into non-decreasing order.

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 top-down merge sort approach is a methodology that uses the recursion mechanism. It starts from the Top and proceeds downwards, with each recursive turn asking the same question, such as “What is required to be done to sort the array?” and having an answer as, “Split an array into two, make a recursive call, and merge the results.” until one gets to the bottom of an array tree.

Example

Okay, before going to the code, first understand a model of Merge Sort; this will help you know the code.

Let us consider a list of integers:

So, as per the algorithm, we first need to divide the list length (n) into two parts until they are divided into one node.

So here, n=7 now n/2=3 . Thus, the first part will be 3 integers, and the second part will be of 7-3=4 part.

Note: If the list size is even, both sides will be divided equally. But for the case of ODD smaller size will be on the left side, and the more significant will be on the right side.

So, after Step 1, the list will be divided like the following.

Like this again, we will divide each of the lists by 2. The left side list will be in 1+2, and the right side will appear in the 2+2 part. The same thing will happen again until they all get separated. So, here we will see the final list after the divide method. See the following figure.

Okay, after all the Divide operations are performed, we will perform Conquer and Sort the two subsequences recursively using merge Sort and Combine, that is, Merge the two sorted subsequences to produce the sorted answer operation .

So here, we will see what will be the result after each step:

So, what happened here is… First, it compared two sub-sequences; for example, 63 and 93 are checked and placed in ascending order after the merge. Similarly, 27 and 21 are checked and then placed ascending after merging.

Again in step two, 43,63,93 were checked and placed in ascending order after merge. In this way, we got our final shortlist.

15

21

24

27

43

63

93

Pseudo Code for Merge Sort

procedure mergesort( var a as array ) if ( n == 1 ) return a var l1 as array = a[0] . a[n/2] var l2 as array = a[n/2+1] . a[n] l1 = mergesort( l1 ) l2 = mergesort( l2 ) return merge( l1, l2 ) end procedure procedure merge( var a as array, var b as array ) var c as array while ( a and b have elements ) if ( a[0] > b[0] ) add b[0] to the end of c remove b[0] from b else add a[0] to the end of c remove a[0] from a end if end while while ( a has elements ) add a[0] to the end of c remove a[0] from a end while while ( b has elements ) add b[0] to the end of c remove b[0] from b end while return c end procedure

C++ Merge Sort Program

#include using namespace std; int Merge(int A[],int p, int q,int r) < int n1,n2,i,j,k; //size of left array=n1 //size of right array=n2 n1=q-p+1; n2=r-q; int L[n1],R[n2]; //initializing the value of Left part to L[] for(i=0;i//initializing the value of Right Part to R[] for(j=0;j i=0,j=0; //Comparing and merging them //into new array in sorted order for(k=p;i else < A[k]=R[j++]; >> //If Left Array L[] has more elements than Right Array R[] //then it will put all the // reamining elements of L[] into A[] while(i //If Right Array R[] has more elements than Left Array L[] //then it will put all the // reamining elements of L[] into A[] while(j > //This is Divide Part //This part will Divide the array into //Sub array and then will Merge them //by calling Merge() int MergeSort(int A[],int p,int r) < int q; if(p> int main() < int n; cout>n; int A[n],i; cout>A[i]; //Calling the MergeSort() //First we are passing the array //the start index that is 0 //and the size of the array n MergeSort(A,0,n-1); cout return 0; >

The output is the following.

Time Complexity for Merge Sort

Running time T(n) of Merge Sort:

1. Divide: computing the middle takes Θ(1)
2. Conquer: solving 2 sub-problems takes 2 T ( n /2)
3. Combine: merging n elements takes Θ( n )
4. Total time complexity is the following.

T(n) = Θ(1) if n = 1T(n) = 2T(n/2) + Θ(n) if n > 1 T(n)= 2 T(n/2) + n = 2 ((n/2)log(n/2) + (n/2)) + n = n (log(n/2)) + 2n = n log n – n + 2n = n log n + n = O(n log n )

The above recurrence can be solved using the Recurrence Tree or the Master method. However, it falls in case II of the Master Method, and the solution of the repetition is O(n log n).

The time complexity of the Merge Sort is O(n log n) in all 3 cases (worst, average, and best) as the merge sort divides the array into two halves and takes linear time to merge two halves.

It is one of the most respected algorithms, with the worst-case time complexity being Ο(n log n).

Источник

Merge Sort in C++

Merge sort is one the sorting technique that is used to sort the data in a logical order. It uses divide and conquer approach for sorting the data. Merge sort repeatedly breaks down a list into several sub lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list. In this article, we will read more about merge sort in C++.

Merge Sort in C++

• A file of any size can be sorted using merge sort.
• Elements in the merge sort are divided into two sub list again and again until each sub-list contain only one element.
• After this, the elements are merged to make a sorted list.
• It requires more space and is less efficient

Execution of Merge sort in C++

Merge sort is executed in three steps:-

1.) Divide Step:

First of all the array will be divide in to N sub list, until each sub list contains only one element.

2.) Conquer Step:

Take two sub list and place them in logical order.

3.) Combine Step:

Combine the elements back by merging the two sorted sub list into a sorted sequence.

Program for merge sort in C++

We will look at two different methods, both have the same time complexity with the difference that –

• Method 1 – Uses two temp subarrays
• Method 2 – Uses 1 temp subarray

The combined size of two temp subarrays in method 1 is the same as the whole array in method 2. So the space complexity remains the same.

#include using namespace std; void mergeSort(int[],int,int); void merge(int[],int,int,int); void printArray(int arr[], int size) < int i; for(i = 0; i < size; i++)< cout cout int main() < int array[]= ; int i; int size = sizeof(array)/sizeof(array[0]); printArray(array, size); mergeSort(array, 0, size-1); printArray(array, size); > void mergeSort(int a[], int left, int right) < int mid; if(left < right) < // can also use mid = left + (right - left) / 2 // this can avoid data type overflow mid = (left + right)/2; // recursive calls to sort first half and second half subarrays mergeSort(a, left, mid); mergeSort(a, mid + 1, right); merge(a, left, mid, right); >> void merge(int arr[], int left, int mid, int right) < int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; // create temp arrays to store left and right subarrays int L[n1], R[n2]; // Copying data to temp arrays L[] and R[] for (i = 0; i < n1; i++) L[i] = arr[left + i]; for (j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; // here we merge the temp arrays back into arr[l..r] i = 0; // Starting index of L[i] j = 0; // Starting index of R[i] k = left; // Starting index of merged subarray while (i < n1 && j < n2) < // place the smaller item at arr[k] pos if (L[i] else < arr[k] = R[j]; j++; >k++; > // Copy the remaining elements of L[], if any while (i < n1) < arr[k] = L[i]; i++; k++; >// Copy the remaining elements of R[], if any while (j < n2) < arr[k] = R[j]; j++; k++; >>

Output

8 4 5 1 3 9 0 2 7 6 0 1 2 3 4 5 6 7 8 9

#include using namespace std; void mergeSort(int[],int,int); void merge(int[],int,int,int); void printArray(int arr[], int size) < int i; for(i = 0; i < size; i++)< cout cout int main() < int array[]= ; int i; int size = sizeof(array)/sizeof(array[0]); printArray(array, size); mergeSort(array, 0, size-1); printArray(array, size); > void mergeSort(int a[], int left, int right) < int mid; if(left < right) < // can also use mid = left + (right - left) / 2 // this can avoid data type overflow mid = (left + right)/2; // recursive calls to sort first half and second half subarrays mergeSort(a, left, mid); mergeSort(a, mid + 1, right); merge(a, left, mid, right); >> void merge(int a[], int left, int mid, int right) < int i = left; // starting index of left subarray int j = mid + 1; // starting index of right subarray int index = left; // used to place items in temp[] int temp[10]; while(ielse < temp[index] = a[j]; j = j+1; >index++; > // i > mid would mean all items for left // subarray were successfully placed, and there // must be unplaced right subarray items if(i>mid) < while(j<=right) < temp[index] = a[j]; index++; j++; >> // else all items of right subarray must have // been placed and there must be // unplaced items in the left-subarray else < while(i<=mid) < temp[index] = a[i]; index++; i++; >> int p = left; // left index of subarray // by now index would have reached right // most index of right subarray // placing all items of temp[] into actual array a[] while(p < index) < a[p]=temp[p]; p++; >>

Output

8 4 5 1 3 9 0 2 7 6 0 1 2 3 4 5 6 7 8 9

Источник