Merge Sort - potatoscript/dsa GitHub Wiki

🧩 Merge Sort – Divide and Conquer

Merge Sort is one of the most efficient sorting algorithms and follows the Divide and Conquer approach. This means it breaks down a large problem (sorting an entire array) into smaller, easier-to-solve subproblems (sorting smaller arrays), and then combines the solutions to those subproblems to form the final solution.

Merge Sort divides the unsorted array into two halves, sorts each half, and then merges the sorted halves back together. The beauty of Merge Sort lies in its ability to handle large datasets efficiently and its consistent O(n log n) time complexity.

📖 How Does Merge Sort Work?

Merge Sort follows a three-step process:

Divide: Split the array into two halves.
Conquer: Recursively split the halves until you have arrays of size 1 (which are inherently sorted).
Combine: Merge the sorted halves back together to form a sorted array.

🚀 Step-by-Step Explanation of Merge Sort

Let’s take an unsorted array to demonstrate how Merge Sort works:

[5, 2, 9, 1, 5, 6]

Step 1: Divide

Split the array into two halves:
```
[5, 2, 9]   and   [1, 5, 6]
```

Step 2: Recursively Divide

Split the left half [5, 2, 9] further into:
```
[5]   and   [2, 9]
```
Split the right half [1, 5, 6] further into:
```
[1]   and   [5, 6]
```

Step 3: Continue Dividing

Split [2, 9] into:
```
[2]   and   [9]
```
Split [5, 6] into:
```
[5]   and   [6]
```

Now we have an array where each subarray contains just one element, and we can start merging them back together.

Step 4: Combine (Merge)

Now, we merge the subarrays, comparing their elements and sorting them as we go:

Merge [2] and [9]:
- Compare 2 and 9. Since 2 is smaller, the sorted array is [2, 9].
Merge [5] and [6]:
- Compare 5 and 6. Since 5 is smaller, the sorted array is [5, 6].

Step 5: Merge Larger Subarrays

Now, merge the larger subarrays:

Merge [5] and [2, 9]:
- Compare 5 with 2: Since 2 is smaller, the sorted array is [2].
- Compare 5 with 9: Since 5 is smaller, the sorted array is [2, 5].
- Now add 9: The sorted array is [2, 5, 9].
Merge [1] and [5, 6]:
- Compare 1 with 5: Since 1 is smaller, the sorted array is [1].
- Now add 5 and 6: The sorted array is [1, 5, 6].

Step 6: Final Merge

Finally, merge [2, 5, 9] and [1, 5, 6]:

Compare 2 with 1: Since 1 is smaller, the sorted array is [1].
Compare 2 with 5: Since 2 is smaller, the sorted array is [1, 2].
Compare 5 with 5: They are equal, so we can add either one to the sorted array: [1, 2, 5].
Compare 5 with 6: Since 5 is smaller, the sorted array is [1, 2, 5, 5].
Compare 9 with 6: Since 6 is smaller, the sorted array is [1, 2, 5, 5, 6].
Finally, add 9: The sorted array is [1, 2, 5, 5, 6, 9].

Now the array is fully sorted!

🧑‍💻 C# Code for Merge Sort

Here is the C# implementation of Merge Sort:

using System;

public class MergeSortExample
{
    // Merge Sort Method
    public static void MergeSort(int[] arr)
    {
        if (arr.Length <= 1) return;

        int mid = arr.Length / 2;

        // Split the array into two halves
        int[] left = new int[mid];
        int[] right = new int[arr.Length - mid];

        Array.Copy(arr, 0, left, 0, mid);
        Array.Copy(arr, mid, right, 0, arr.Length - mid);

        // Recursively sort the two halves
        MergeSort(left);
        MergeSort(right);

        // Merge the sorted halves
        Merge(arr, left, right);
    }

    // Method to merge two sorted arrays
    private static void Merge(int[] arr, int[] left, int[] right)
    {
        int i = 0, j = 0, k = 0;

        // Merge the arrays while comparing the elements
        while (i < left.Length && j < right.Length)
        {
            if (left[i] < right[j])
            {
                arr[k] = left[i];
                i++;
            }
            else
            {
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        // If any elements are left in the left array, add them
        while (i < left.Length)
        {
            arr[k] = left[i];
            i++;
            k++;
        }

        // If any elements are left in the right array, add them
        while (j < right.Length)
        {
            arr[k] = right[j];
            j++;
            k++;
        }
    }

    // Main method to run and test Merge Sort
    public static void Main()
    {
        int[] arr = { 5, 2, 9, 1, 5, 6 };

        Console.WriteLine("Unsorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");

        // Call the MergeSort method
        MergeSort(arr);

        Console.WriteLine("\nSorted array:");
        foreach (var num in arr)
            Console.Write(num + " ");
    }
}

🧑‍💻 Explanation of Code:

MergeSort Method: This method divides the array into two halves and recursively calls MergeSort on each half.
Merge Method: This method merges two sorted arrays into a single sorted array by comparing their elements one by one.
The main method tests the MergeSort by applying it to an unsorted array.

🧑‍💻 Output:

When you run the code, the output will look like this:

Unsorted array:
5 2 9 1 5 6 

Sorted array:
1 2 5 5 6 9

📊 Time Complexity of Merge Sort

Best Case: O(n log n) – The time complexity remains O(n log n) even when the array is already sorted.
Worst Case: O(n log n) – In the worst case, Merge Sort still performs O(n log n) comparisons and merges.
Average Case: O(n log n) – The average case is also O(n log n), which is one of the reasons Merge Sort is efficient for large datasets.

💡 Space Complexity of Merge Sort

Space Complexity: O(n) – Merge Sort is not an in-place sorting algorithm, meaning it requires additional space to store the left and right halves of the array during the merge process.

⚡ Why Use Merge Sort?

Efficiency: With its O(n log n) time complexity, Merge Sort is efficient and works well with large datasets.
Stability: Merge Sort is stable, meaning that it preserves the relative order of equal elements.
Parallelizable: Merge Sort can be implemented in parallel, making it suitable for multi-core processors.
Consistent Performance: Unlike other sorting algorithms like Quick Sort, Merge Sort’s performance is not dependent on the initial ordering of elements.

However, Merge Sort requires additional space for the left and right arrays, so for small datasets, simpler algorithms like Insertion Sort may be preferred.