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.

• Tuned mergesort for objects. - where space doesn't matter

4MB

Mergesort.pdf

pdf

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

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.

• 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

Article

Code Dry Run

Space Complexity = O(n)

Time Complexity = O(n log n)

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.

#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] << ' ';
    }
}