Blog / Introduction to the Merge Sort Algorithm

Introduction to the Merge Sort Algorithm

by SW Team

The Merge Sort algorithm is an efficient, general, comparative method for sorting lists or arrays. It is a classic example of a “divide and conquer” algorithm. Merge Sort divides the data set into smaller halves, sorts them, and then merges them back into a single sorted list.

The main advantage of using Merge Sort is its consistent efficiency, which is particularly useful when handling large data sets. Its runtime is generally O(n * log n), which makes it significantly faster than simple sorting algorithms such as Bubble Sort or Insertion Sort, especially on large lists.

Merge Sort is a stable sort algorithm, which means that if two elements have the same value, it preserves the original order in which they appear. This is crucial in situations where the order of equal elements must be maintained, for example, in lists of events that must follow a specific chronological order, even if they occur on the same date.

cta:cloud_so

In the following, we show how the Merge Sort algorithm is implemented in three different programming languages: Python, C and Java.

Implementation of Merge Sort in Python

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

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

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

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

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1
     # Example of use
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("Array ordenado:", arr)

Implementation of Merge Sort in C

#include <stdio.h>
#include <stdlib.h>

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

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    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++;
    }

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

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

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(arr, l, m, r);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    mergeSort(arr, 0, arr_size - 1);

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

    return 0;
}

Implementación de Merge Sort en Java

public class MergeSort {
    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++;
        }
    }

    void sort(int arr[], int l, int r) {
        if (l < r) {
            int m = l + (r - l) / 2;

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

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

    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length - 1);

        System.out.println("Array ordenado:");
        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

In conclusion, Merge Sort is a highly efficient and reliable sorting algorithm, ideal for handling large volumes of data due to its consistent time complexity of O(n * log n).

Although its implementation may be slightly more complex than other simpler sort algorithms, its performance and reliability benefits justify its use in environments that demand high efficiency and accuracy. In summary, choosing Merge Sort is opting for a robust and efficient solution in the field of sorting algorithms.

cta:hosting

i