The Royal Coding
Binary Search Bubble Sort Build A Max Heap Build A Min Heap Graph Traversal Heap Sort Implementing A Basic Hash Table Implementing A Binary Search Tree Implementing A Queue Implementing A Stack Insertion Sort Length Of Linked List Linear Search Linked Lists Merge A Two Sorted Linked List Merge Sort Quick Sort Redix Sort Reverse A Linked List Selection Sort Ternary Search Suffix Automata Construction

Python/C/C++/JAVA

Advanced Practice Programs with Code and Concept

By D.S

Merge Sorting

Merge sort is a popular sorting algorithm used in computer science to arrange a set of data in ascending or descending order. It works by dividing the data into smaller subsets and then merging them back together, comparing and rearranging elements as it goes along. Merge sort can be implemented in several programming languages including C, C++, Python, and Java, each with slightly different syntax. However, the basic principles remain the same regardless of the language used. Merge sort has a time complexity of O(n log n), which means that it's efficient for sorting large sets of data. It's also a stable algorithm, meaning that items with equal values are kept in their original order. Overall, merge sort is a reliable and powerful tool for managing large amounts of data efficiently.

(a.) C Program

#include <stdio.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // Create temp arrays
    int L[n1], R[n2];

    // Copy data to temp arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Merge the temp arrays back into arr[l..r]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for large l and r
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {5, 2, 7, 1, 9, 3};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    mergeSort(arr, 0, arr_size - 1);

    printf("Sorted array: ");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}
Output:-
Original array: 5 2 7 1 9 3
Sorted array: 1 2 3 5 7 9

(b.) C++ Program

#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temporary arrays
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Merge the temporary arrays back into arr[l..r]
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for large l and r
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

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

int main() {
    int arr[] = {5, 2, 7, 1, 9, 3};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < arr_size; i++)
        cout << arr[i] << " ";
    cout << endl;

    mergeSort(arr, 0, arr_size - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < arr_size; i++)
        cout << arr[i] << " ";
    cout << endl;

    return 0;
}
Output:-
Original array: 5 2 7 1 9 3
Sorted array: 1 2 3 5 7 9

(c.) Python Program

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

arr = [5, 2, 7, 1, 9, 3]
print("Original array:", arr)

merge_sort(arr)
print("Sorted array:", arr)
Output:-
Original array: 5 2 7 1 9 3
Sorted array: 1 2 3 5 7 9

(d.) Java Program

import java.util.Arrays;
  
  public class MergeSort {
      public static void merge(int arr[], int l, int m, int r) {
          int n1 = m - l + 1;
          int n2 = r - m;
  
          int L[] = new int[n1];
          int R[] = new int[n2];
  
          for (int i = 0; i < n1; ++i)
              L[i] = arr[l + i];
          for (int j = 0; j < n2; ++j)
              R[j] = arr[m + 1 + j];
  
          int i = 0, j = 0;
          int k = l;
          while (i < n1 && j < n2) {
              if (L[i] <= R[j]) {
                  arr[k] = L[i];
                  i++;
              } else {
                  arr[k] = R[j];
                  j++;
              }
              k++;
          }
  
          while (i < n1) {
              arr[k] = L[i];
              i++;
              k++;
          }
  
          while (j < n2) {
              arr[k] = R[j];
              j++;
              k++;
          }
      }
  
      public static void mergeSort(int arr[], int l, int r) {
          if (l < r) {
              int m = (l + r) / 2;
  
              mergeSort(arr, l, m);
              mergeSort(arr, m + 1, r);
  
              merge(arr, l, m, r);
          }
      }
  
      public static void main(String[] args) {
          int arr[] = {5, 2, 7, 1, 9, 3};
          System.out.println("Original array: " + Arrays.toString(arr));
  
          mergeSort(arr, 0, arr.length - 1);
  
          System.out.println("Sorted array: " + Arrays.toString(arr));
      }
  }
Output:-
Original array: [5, 2, 7, 1, 9, 3]
Sorted array: [1, 2, 3, 5, 7, 9]

How did you feel about this post?

😍 🙂 😐 😕 😡

Was this helpful?

👍 👎