# Merge Sort

The merge sort function is a very efficient sorting algorithm. It is a divide-and-conquer algorithm, which means it breaks down the problem into smaller and smaller subproblems until they can be solved easily. This makes it a very efficient algorithm for sorting large arrays.

* &#x20;Tuned **mergesort** for <mark style="color:red;">objects</mark>. - where space doesn't matter

{% file src="/files/L8HVLSRDYVTR1dCjW9TZ" %}

### How does Merge Sort work?

> Merge sort is a recursive algorithm that continuously splits the array in half until it cannot be further divided i.e., the array has only one element left (an array with one element is always sorted). Then the sorted subarrays are merged into one sorted array.

### **Applications of Merge Sort:**

* **Sorting large datasets:** Merge sort is particularly well-suited for sorting large datasets due to its guaranteed worst-case time complexity of O(n log n).
* **External sorting:** Merge sort is commonly used in external sorting, where the data to be sorted is too large to fit into memory.
* **Custom sorting:** Merge sort can be adapted to handle different input distributions, such as partially sorted, nearly sorted, or completely unsorted data.
* [**Inversion Count Problem**](https://www.geeksforgeeks.org/inversion-count-in-array-using-merge-sort/)

### **Advantages of Merge Sort:**

* **Stability**: Merge sort is a stable sorting algorithm, which means it maintains the relative order of equal elements in the input array.
* **Guaranteed worst-case performance:** Merge sort has a worst-case time complexity of O(N logN), which means it performs well even on large datasets.
* **Parallelizable**: Merge sort is a naturally parallelizable algorithm, which means it can be easily parallelized to take advantage of multiple processors or threads.

### **Drawbacks of Merge Sort:**

* **Space complexity:** Merge sort requires additional memory to store the merged sub-arrays during the sorting process.&#x20;
* **Not in-place:** Merge sort is not an in-place sorting algorithm, which means it requires additional memory to store the sorted data. This can be a disadvantage in applications where memory usage is a concern.
* **Not always optimal for small datasets:** For small datasets, Merge sort has a higher time complexity than some other sorting algorithms, such as insertion sort. This can result in slower performance for very small datasets.

## `Q1:`    [Merge Sort](https://www.codingninjas.com/studio/problems/merge-sort_920442?)

## [Article](https://www.geeksforgeeks.org/merge-sort/)

## Code [Dry Run](https://drive.google.com/file/d/1AHjUGsycUXjYMzpjN74sXu5ZwLmOWzZX/view?usp=drive_link)

## Space Complexity = O(n)

## Time Complexity = O(n log n)

<figure><img src="/files/gpZKXTZ0a52n2nStKuwO" alt=""><figcaption></figcaption></figure>

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

```cpp
#include <iostream>
using namespace std;

// A function to merge two sorted subarrays into one
void Merging(int *arr, int mid, int s, int e) {

    int len1 = mid-s+1;
    int len2 = e-mid;
    
    // Create temporary arrays to store the subarrays
    int *first = new int[len1];
    int *second = new int[len2];

    int mainArrayIndex = s;

    // Copy the data from the original array to the temporary arrays
    for (int i = 0; i < len1; i++)
        first[i] = arr[mainArrayIndex++];

    for (int i = 0; i < len2; i++)
        second[i] = arr[mainArrayIndex++];
    
    // Initialize the indices for the subarrays and the merged array
    int i = 0, j = 0, k = s;
    
    // Merge the subarrays by comparing their elements
    while (i < len1 && j < len2){
        if(first[i] < second[j])
            arr[k++] = first[i++];
        else
            arr[k++] = second[j++];
    }

    // Copy the remaining elements of the subarrays if any
    while (i < len1)
        arr[k++] = first[i++];
    
    while (j < len2)
        arr[k++] = second[j++];
   
}

void mergeSort(int *arr, int s, int e) {
    if(s >= e)
        return;
    int mid = s+(e-s)/2;

    // Recursively sort the left and right halves of the array
    mergeSort(arr, s, mid);

    mergeSort(arr, mid+1, e);
  
    if (arr[mid] <= arr[mid + 1])
               return;

    Merging(arr, mid, s, e);
}

int main(){
    int n = 7;
    int arr[n] = { 3, 4, 1, 6, 2, 5, 7 };
    mergeSort(arr, 0, n-1);

    for (int i = 0; i < n; i++){
        cout << arr[i] << ' ';
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/sorting-algorithms/merge-sort.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.