# Merge Sort Analysis

Merge sort is a widely used and efficient sorting algorithm based on the divide-and-conquer paradigm. It is an efficient, general-purpose, and comparison-based sorting algorithm that works well for large datasets.

Merge sort works by dividing the input array into two halves, sorting each half recursively using the same algorithm, and then merging the two sorted halves into a single sorted array. The merging process involves comparing the first element of each sorted half and choosing the smaller element, which is then added to the merged array. This process is repeated until all the elements from both halves have been merged.

## Algorithm of Merge Sort

Here is the algorithm for Merge Sort:

1. If the input array has only one element, it is already sorted. Return the input array.
2. Divide the input array into two halves.
3. Sort the first half of the array recursively using the Merge Sort algorithm.
4. Sort the second half of the array recursively using the Merge Sort algorithm.
5. Merge the two sorted halves into a single sorted array. To do this, compare the first element of each sorted half and choose the smaller one to add to the merged array. Repeat this process until all elements from both halves have been merged.
6. Return the merged array.

Here is the pseudocode for Merge Sort:

``````function mergeSort(array)
if length(array) ≤ 1
return array

middle ← length(array) / 2
left ← mergeSort(array[1..middle])
right ← mergeSort(array[middle+1..length(array)])
return merge(left, right)

function merge(left, right)
result ← empty array
while length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left ← rest(left)
else
append first(right) to result
right ← rest(right)

append remaining elements of left to result
append remaining elements of right to result
return result
``````

In this pseudocode, `mergeSort` function takes an array as input and recursively sorts it using the `merge` function. The `merge` function takes two sorted arrays as input and merges them into a single sorted array.

## How does Merge Sort Work?

Let’s consider an example to understand how Merge Sort works:

Suppose we have an unsorted array of integers as follows: `[8, 4, 1, 9, 3, 7, 5, 2]`.

We can sort this array using Merge Sort as follows:

1. Divide the array into two halves: `[8, 4, 1, 9]` and `[3, 7, 5, 2]`.
2. Recursively sort the two halves using Merge Sort.For the first half `[8, 4, 1, 9]`, divide it into two halves again: `[8, 4]` and `[1, 9]`. Recursively sort each half by dividing them further, until we have individual elements: ``, ``, ``, and ``. Now we can start merging the individual elements back together in sorted order: `[4, 8]` and `[1, 9]`. Finally, we can merge the two sorted halves into a single sorted half: `[1, 4, 8, 9]`.For the second half `[3, 7, 5, 2]`, divide it into two halves again: `[3, 7]` and `[5, 2]`. Recursively sort each half by dividing them further, until we have individual elements: ``, ``, ``, and ``. Now we can start merging the individual elements back together in sorted order: `[3, 7]` and `[2, 5]`. Finally, we can merge the two sorted halves into a single sorted half: `[2, 3, 5, 7]`.
3. Merge the two sorted halves from step 2 into a single sorted array. We compare the first element of each sorted half and choose the smaller one to add to the merged array. We repeat this process until all elements from both halves have been merged. In this case, the first elements of the two sorted halves are `1` and `2`, and `1` is smaller. So we add `1` to the merged array. The next two elements are `2` and `3`, and `2` is smaller. We add `2` to the merged array. Continuing this process, we end up with the fully sorted array: `[1, 2, 3, 4, 5, 7, 8, 9]`.

Thus, the Merge Sort algorithm has sorted the unsorted array `[8, 4, 1, 9, 3, 7, 5, 2]` in ascending order.

Example

```// C++ program for Merge Sort
#include <iostream>
using namespace std;

// Merges two subarrays of array[].
// First subarray is arr[begin..mid]
// Second subarray is arr[mid+1..end]
void merge(int array[], int const left, int const mid,
int const right)
{
auto const subArrayOne = mid - left + 1;
auto const subArrayTwo = right - mid;

// Create temp arrays
auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];

// Copy data to temp arrays leftArray[] and rightArray[]
for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];

auto indexOfSubArrayOne = 0,   // Initial index of first sub-array
indexOfSubArrayTwo = 0;    // Initial index of second sub-array
int indexOfMergedArray = left; // Initial index of merged array

// Merge the temp arrays back into array[left..right]
while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo)
{
if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo])
{
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else
{
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}
// Copy the remaining elements of
// left[], if there are any
while (indexOfSubArrayOne < subArrayOne)
{
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}
// Copy the remaining elements of
// right[], if there are any
while (indexOfSubArrayTwo < subArrayTwo)
{
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
delete[] leftArray;
delete[] rightArray;
}

// begin is for left index and end is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int array[], int const begin, int const end)
{
if (begin >= end)
return; // Returns recursively

auto mid = begin + (end - begin) / 2;
mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}

// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
for (auto i = 0; i < size; i++)
cout << A[i] << " ";
}

// Driver code
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
auto arr_size = sizeof(arr) / sizeof(arr);

cout << "Given array is \n";
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "\nSorted array is \n";
printArray(arr, arr_size);
return 0;
}
```

The above program will output:

``````Given array is
12 11 13 5 6 7
Sorted array is
5 6 7 11 12 13 ``````

## Complexity Analysis of Merge Sort

The time complexity of Merge Sort in the worst case is O(n log n), where n is the number of elements to be sorted. The space complexity of the algorithm is also O(n).

The reason for the time complexity is that Merge Sort divides the input array into two halves recursively until there is only one element in each half. This process takes log n recursive calls. After that, the algorithm starts merging the sorted sub-arrays into larger sorted sub-arrays. The merging process takes O(n) time, as it needs to compare each element in the two sub-arrays once. Since there are log n levels of recursion, the total time complexity of the algorithm becomes O(n log n).

In terms of space complexity, Merge Sort needs to create temporary arrays during the merging process. The size of these arrays is proportional to the size of the original array being sorted. Therefore, the space complexity of the algorithm is O(n).

Although Merge Sort has a worst-case time complexity of O(n log n), it is slower than other sorting algorithms such as Quick Sort and Heap Sort due to the overhead of the recursive calls and the need to create temporary arrays. However, Merge Sort is a stable sorting algorithm, which means that it preserves the relative order of equal elements. It is also a good choice for sorting linked lists, where random access to elements is not possible.

## Where is the Merge sort algorithm used?

Merge Sort is a popular algorithm used for sorting large amounts of data efficiently. It is commonly used in various applications such as:

1. Sorting data in databases and spreadsheets
2. Sorting arrays and linked lists in programming languages such as Java and Python
3. Sorting elements in data visualization and analysis tools
4. Implementing parallel algorithms in distributed computing environments
5. External sorting of large files where the data cannot be held in memory all at once.

Overall, Merge Sort is a versatile algorithm that can be applied to a wide range of problems that require sorting large amounts of data.

1. Merge Sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements in the input sequence.
2. It has a worst-case time complexity of O(n log n), which is optimal for comparison-based sorting algorithms.
3. Merge Sort is a divide-and-conquer algorithm, which makes it easier to implement and understand than other complex algorithms.
4. It is efficient in sorting large datasets and can be used for external sorting of large files.
5. Merge Sort is a parallelizable algorithm, which means it can be used in parallel computing environments for faster processing of large datasets.