Merge Sort Analysis

Hi everyone, inside this article we will see the concept about 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: [8], [4], [1], and [9]. 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: [3], [7], [5], and [2]. 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[0]);

  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.

Advantages of Merge Sort:

  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.

Disadvantages of Merge Sort:

  1. Merge Sort requires additional space for merging the sub-arrays, which can be a constraint in memory-constrained environments.
  2. It has a relatively high overhead due to the recursive calls and the need to create temporary arrays, which can make it slower than other sorting algorithms for small datasets.
  3. Merge Sort is not an in-place sorting algorithm, meaning that it needs additional memory to sort the input sequence.
  4. Although it has a worst-case time complexity of O(n log n), it may not be the fastest algorithm for all cases. For example, Quick Sort may be faster for small to medium-sized datasets.
  5. Merge Sort has a non-linear running time, which can be difficult to analyze and optimize.

We hope this article helped you to understand Merge Sort Analysis in a very detailed way.

Online Web Tutor invites you to try Skillshike! Learn CakePHP, Laravel, CodeIgniter, Node Js, MySQL, Authentication, RESTful Web Services, etc into a depth level. Master the Coding Skills to Become an Expert in PHP Web Development. So, Search your favourite course and enroll now.

If you liked this article, then please subscribe to our YouTube Channel for PHP & it’s framework, WordPress, Node Js video tutorials. You can also find us on Twitter and Facebook.