Merge Sort

Merge Sort

Merge Sort is one of the most useful sorting algorithms and efficient sorting algorithm and it is based on the Divide and Conquer Algorithm principle. Mergesort is like to the quicksort algorithm and it uses the divide and conquer approach to sort the elements.

Algorithm

MergeSort(A, p, r):
    if p > r 
        return
    q = (p+r)/2
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

 

 

Example

Suppose the elements of array are –

 

Merge sort

 

According to the mergesort algorithm, firstly divide the given array into two equal parts.

There are eight elements in the given array, so it is divided them into two arrays of size four

 

Merge sort

 

Now, again divide two arrays into parts. As they have size 4, so divide into new arrays of size 2.

 

Merge sort

 

Again divide these divided arrays to get the atomic value that can’t be further divided.

 

Merge sort

 

And now combine these array in the same manner they were broken.

In combining, firstly, compare the element of each array and then combine these array into another array in sorted order.

So, first compare 12 and 31, they both are in sorted positions. After that compare the  25 and 8, and in the list of two values, put 8 first and then 25. Now, compare 32 and 17, sort them and put 17 first folthen put 32. Then, compare 40 and 42, and place these array in sequentially.

 

Merge sort

 

In the next iteration of combining, compare the arrays with two values and merge these arrays into an array of found values in sorted order.

 

Merge sort

 

Now, there is a final merging the arrays and the array look like –

 

Merge sort

 

Now,

Array is completely sorted

 

Program for merge sort in C

#include <stdio.h>

void merge(int arr[], int p, int q, int r) {

  int n1 = q - p + 1;
  int n2 = r - q;

  int L[n1], M[n2];

  for (int i = 0; i < n1; i++)
    L[i] = arr[p + i];
  for (int j = 0; j < n2; j++)
    M[j] = arr[q + 1 + j];

  int i, j, k;
  i = 0;
  j = 0;
  k = p;

  while (i < n1 && j < n2) {
    if (L[i] <= M[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = M[j];
      j++;
    }
    k++;
  }

  while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < n2) {
    arr[k] = M[j];
    j++;
    k++;
  }
}

// Divide the array into 2 subarrays, sort and merge them
void mergeSort(int arr[], int l, int r) {
  if (l < r) {

    int m = l + (r - l) / 2;

    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);

    // Merge the sorted subarrays
    merge(arr, l, m, r);
  }
}

// Print the array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

// Driver program
int main() {
  int arr[] = {6, 5, 12, 10, 9, 1};
  int size = sizeof(arr) / sizeof(arr[0]);

  mergeSort(arr, 0, size - 1);

  printf("Sorted array: \n");
  printArray(arr, size);
}

 

Output

Sorted array: 
1 5 6 9 10 12

 

Program for merge sort in C++

#include <iostream>
using namespace std;

// Merge two subarrays 
void merge(int arr[], int p, int q, int r) {
  
  // Create L ← A[p..q] and M ← A[q+1..r]
  int no1 = q - p + 1;
  int no2 = r - q;

  int L[no1], M[no2];

  for (int i = 0; i < no1; i++)
    L[i] = arr[p + i];
  for (int j = 0; j < no2; j++)
    M[j] = arr[q + 1 + j];

  int i, j, k;
  i = 0;
  j = 0;
  k = p;

    while (i < no1 && j < no2) {
    if (L[i] <= M[j]) {
      arr[k] = L[i];
      i++;
    } else {
      arr[k] = M[j];
      j++;
    }
    k++;
  }

  while (i < no1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  while (j < no2) {
    arr[k] = M[j];
    j++;
    k++;
  }
}

// Divide the array into two subarrays, sort and merge them
void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;

    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);

    // Merge the sorted subarrays
    merge(arr, l, m, r);
  }
}

// Print the array
void printArray(int arr[], int size) {
  for (int i = 0; i < size; i++)
    cout << arr[i] << " ";
  cout << endl;
}

int main() {
  int arr[] = {6, 5, 12, 10, 9, 1};
  int size = sizeof(arr) / sizeof(arr[0]);

  mergeSort(arr, 0, size - 1);

  cout << "Sorted array: \n";
  printArray(arr, size);
  return 0;
}

Output

Sorted array: 
1 5 6 9 10 12

 

Program for merge sort in Python

def mergeSort(array):
    if length(array) > 1:

        a = length(array)//2
        B = array[:r]
        C = array[r:]

        # Sort the two parts
        mergeSort(B)
        mergeSort(C)

        i = j = k = 0

        while i < length(B) and j < length(c):
            if B[i] < B[j]:
                array[k] = B[i]
                i += 1
            else:
                array[k] = C[j]
                j += 1
            k += 1

        while i < length(B):
            array[k] = B[i]
            i += 1
            k += 1

        while j < length(C):
            array[k] = C[j]
            j += 1
            k += 1


# Print the array
def printList(array):
    for i in range(length(array)):
        print(array[i], end=" ")
    print()


# Driver program
if __name__ == '__main__':
    array = [6, 5, 12, 10, 9, 1]

    mergeSort(array)

    print("Sorted array is: ")
    printList(array)

Output

Sorted array is: 
1 5 6 9 10 12

Program for merge sort in Java

class MergeSort {

  // Merge two subarrays 
  void merge(int arr[], int p, int q, int r) {

    int no1 = q - p + 1;
    int no2 = r - q;

    int B[] = new int[no1];
    int C[] = new int[no2];

    for (int i = 0; i < no1; i++)
      L[i] = arr[p + i];
    for (int j = 0; j < no2; j++)
      M[j] = arr[q + 1 + j];

    // current index 
    int i, j, k;
    i = 0;
    j = 0;
    k = p;

      while (i < no1 && j < no2) {
      if (B[i] <= C[j]) {
        arr[k] = B[i];
        i++;
      } else {
        arr[k] = B[j];
        j++;
      }
      k++;
    }

    while (i < n1) {
      arr[k] = B[i];
      i++;
      k++;
    }

    while (j < no2) {
      arr[k] = C[j];
      j++;
      k++;
    }
  }

  // Divide the array into 2 subarrays, sort and merge them
  void mergeSort(int arr[], int l, int r) {
    if (l < r) {

      int m = (l + r) / 2;

      mergeSort(arr, b, c);
      mergeSort(arr, c+ 1, r);

      // Merge the sorted subarrays
      merge(arr, b, c, r);
    }
  }

  // Print the array
  static void printArray(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }

  // Driver program
  public static void main(String args[]) {
    int arr[] = { 6, 5, 12, 10, 9, 1 };

    MergeSort ob = new MergeSort();
    ob.mergeSort(arr, 0, arr.length - 1);

    System.out.println("Sorted array:");
    printArray(arr);
  }
}

Output

Sorted array:
1 5 6 9 10 12

Time Complexity

Best Case Complexity: 

O(n*log n)

Worst Case Complexity: 

O(n*log n)

Average Case Complexity:

 O(n*log n)

Space Complexity

The space complexity is O(n).

 

Read more, Insertion sort

 

Share this post

Leave a Reply

Your email address will not be published. Required fields are marked *