# How merge sort works ?

## For arrays

1. Then list is sorted into halves till it cannot be further divided.
2. These smaller lists are merged into new lists in sorted way.

1. If step 1 does not follow then divide the linked list into 2 halves.
2. After that the 2 halves are sorted.
3. Then the halves are merged and head pointer is updated using headref(you can take any other variable ).

# Pseudocode

1. Assign left as zero and right as n-1(where n is the number of variables).
2. Calculate mid by (left + right)/2.
3. Call function on (left,mid) and (mid+1,rear) and continue till left<right, else return.
4. Then merge the above subproblems.

# Code(for an array)

`#include <bits/stdc++.h>using namespace std;// We create two subarrays // First from arr[x..p] and second from arr[p+1..y]// where x is leftmost index and y is rightmost indexvoid func(int arr[], int x, int p, int y){ int m = p — x + 1; int n = y — p; // Here we are creating temporary arrays as arr1 and arr2 int arr1[m], arr2[n];//copying data to temporary arraysfor (int i = 0; i < m; i++) {arr1[i] = arr[x + i];} for (int j = 0; j < n; j++) {arr2[j] = arr[p + 1 + j];} int i = 0;int j = 0;int k = x; //declaring variables i,j,k; while (i<m && j<n) { if (arr1[i] <= arr2[j])  { arr[k] = arr1[i]; i++; } else  { arr[k] = arr2[j]; j++; } k++; } // here we are copying remaining elements of arr1 if there are any while (i < m) { arr[k] = arr1[i]; i++; k++; } // here we are copying remaining elements of arr2 if there are any while (j < n) { arr[k] = arr2[j]; j++; k++; }}void func1(int arr[],int x,int y){ if(x<y) { int p =x+ (y-x)/2; //middle element func1(arr,x,p); //merge sort for first half func1(arr,p+1,y); //merge sort for second half func(arr,x,p,y); //merging both halves}}int main(){ int n; //taking size of array as input from user cin>>n; int arr[n]; for(int i=0;i<n;i++) { cin>>arr[i];} //taking values of array as input from user cout << “Given array is: “; for(int i=0;i<n;i++) { cout<<arr[i]<<” “; //printing the original array } func1(arr, 0, n — 1); //calling function func1 cout << “\nSorted array is: “; for(int i=0;i<n;i++) { cout<<arr[i]<<” “; //printing the sorted array } return 0;}`

# Output

1. Merge sort works more efficiently and faster on larger data sets.
2. Merge sort is a stable sorting technique.

1. Its space complexity is O(n) which means it requires a lot of space for creating a auxiliary array which it uses for storing.
2. Even if the array is sorted, it will go through the whole process.

# Differences between merge sort and quick sort

1. Dataset — Quick sort is generally preferred for smaller arrays and is not preferred for larger datasets whereas merge sort works fine on any size of data.
2. Storage space — Quick sort does not require any extra space whereas merge sort requires extra memory for auxiliary arrays.
3. Efficiency — Quick sort works more efficiently and faster for shorter dataset whereas merge sort works more efficiently and faster for bigger dataset.
4. Preference — Quick sort if preferred for arrays whereas merge sort is preferred for linked list.
5. Method of sorting — In quick sort the data is stored in main memory, therefore it is internal sorting method whereas in merge sort, the data which is to be sorted cannot be stored in memory and it requires temporary memory ,so it is external sorting method.
6. Stability — Quick sort is not stable but it can be made stable by doing some changes in the code whereas merge sort is stable.
7. Locality of preference — It is good in case of quick sort and poor in case of merge sort.

CSE student