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

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);

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)