Forem

Fabrizio Bagalà
Fabrizio Bagalà

Posted on • Edited on

1 1

Merge Sort

Merge Sort is a sorting algorithm that employs the divide et impera strategy. This approach breaks down a complex issue into smaller, manageable problems, solves these smaller problems, and finally combines these solutions to address the original issue.

In this algorithm, sorting is achieved by continuously having a list of items until individual sublists have only one element each. It then merges these sublists in a sorted manner to form a larger list. This process is repeated until all the sublists are combined back into one large sorted list.

How it works

The functioning of Merge Sort can be categorized into two main phases:

  1. Division phase: Involves dividing the input list recursively until each list comprises only one element, which is, by definition, sorted.
  2. Merging phase: Consists of combining two sorted lists into one sorted list. This is accomplished by comparing the first elements of each list and picking the smaller ones for the new list. This process continues until all elements are exhausted from both lists.

Here is a simple implementation in C#:

public void MergeSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        var middle = left + (right - left) / 2;

        MergeSort(arr, left, middle);
        MergeSort(arr, middle + 1, right);

        Merge(arr, left, middle, right);
    }
}

public void Merge(int[] arr, int left, int middle, int right)
{
    var n = right - left + 1;
    var temp = new int[n];
    var i = left;
    var j = middle + 1;
    var k = 0;

    while (i <= middle && j <= right)
    {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }

    while (i <= middle)
    {
        temp[k++] = arr[i++];
    }

    while (j <= right)
    {
        temp[k++] = arr[j++];
    }

    Array.Copy(temp, 0, arr, left, n);
}
Enter fullscreen mode Exit fullscreen mode

To use the above implementation, you simply need to call the MergeSort method with your array and the lowest and highest indices as arguments. For instance, if you have an array of integers named arr, you would initiate the sorting process with the following method call:

MergeSort(arr, 0, arr.Length - 1);
Enter fullscreen mode Exit fullscreen mode

This will sort the arr in ascending order.

Time complexity

The time complexity is O(n log n) in both the average and worst-case scenarios, where n represents the number of elements to be sorted.

This complexity is achievable because Merge Sort divides the array in half at the division stage, creating a binary tree structure. The algorithm then takes a linear time O(n) to merge these halves in an orderly manner. This combination of splitting and merging results in a time complexity of O(n log n), with log n as a result of halving the array and n resulting from the merging process.

Space complexity

While Merge Sort performs excellently in terms of time complexity, it is less efficient when it comes to space complexity. Its space complexity is O(n), where n represents the number of elements to be sorted. This is because the algorithm requires auxiliary space to temporarily hold the elements being merged during the merge phase.

The auxiliary space is crucial as it allows for the comparison of elements between two sorted halves and the building of the new sorted list. For each level of recursion during the merge phase, an auxiliary array of size n is allocated, which leads to the O(n) space complexity.

Conclusion

In conclusion, Merge Sort, with its methodical divide et impera approach, is a brilliant example of systematic problem-solving in action. Its ability to efficiently handle vast data sets, turning a seemingly overwhelming task into a manageable one, is truly remarkable. However, it is essential to remember that its usefulness, like that of any algorithm, is determined by the unique constraints and requirements of the task at hand.

References

  • Algoritmi e programmazione in C di Francesco Oliveri, Aracne editrice (Italian book)

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay