MERGE SORT ALGORITHM IN C AND C++

Merge Sort is a powerful and efficient algorithm for sorting arrays, commonly used in various applications due to its stable sorting nature and O(n log n) time complexity. It follows the divide-and-conquer approach, recursively splitting the array into smaller subarrays until each subarray contains a single element. These smaller arrays are then merged back together in a sorted order.
This tutorial explores the step-by-step implementation of Merge Sort in C and C++, focusing on the mergeArrays function, which is central to the merging process. We'll discuss the logic behind merging two sorted arrays and whether a for loop can replace the two while loops in this process, providing insights into both the efficiency and clarity of your code.

Merge Sort is a widely used algorithm that is considered more efficient than simpler algorithms like Bubble Sort or Insertion Sort. The key reason lies in its time complexity: Merge Sort consistently performs at 𝑂(𝑛log𝑛) in the worst case, making it significantly faster for large datasets compared to the quadratic time complexity 𝑂(𝑛²) of Bubble Sort and Insertion Sort. While Quick Sort is another efficient algorithm with an average-case performance of 𝑂(𝑛log𝑛) , its worst-case performance can degrade to 𝑂(𝑛²) , especially if the pivot selection is poor. In contrast, Merge Sort not only guarantees 𝑂(𝑛log𝑛) in all cases but is also a stable sort, meaning it maintains the relative order of equal elements, a property that can be particularly useful in certain applications.

Merge Sort is an algorithm that is more efficient than bubble sorting or insert sorting, but not faster than Quick Sort. Merge Sort follows the divide-and-conquer paradigm, where the initial array is recursively divided into two approximately equal subarrays, left and right. This division creates subproblems that are smaller and easier to solve. The process continues until each subarray is reduced to a single element, which by definition is already sorted. The procedure is then repeated until two elementary arrays of 1 element are reached. Then begins sorting these elementary arrays, and then merging them into larger arrays. In order to form a sorted array when merging, one member of the left and one member of the right subarray is compared in order, and a larger subarray is composed of them, which contains the members of both these small arrays, but in the correct order, ie. . sorted either in ascending or descending order. E.g.
This approach is a classic example of the divide-and-conquer paradigm, where a complex problem is broken down into simpler subproblems. By solving these subproblems independently and then combining their solutions, Merge Sort efficiently handles the entire sorting process.
Suppose we have the following sequence that needs to be sorted in ascending order:

Figure 1: Merge Sort Algorithm- Initial Array

VIDEO: Merge sort algorithm

The task can be solved by recursion.
The process of recursively calling a sorting function begins after entering or initialisation of an array. The function can be called e.g. mergeSort and pass the array itself, the starting position, the end position and the number of elements as a parameter.
The prototype of this function could be:

void mergeSort(int a[ ], int l,int r,int n);

The function should do the following:

Finds the middle position approximately to determine the left (0, m) and right part of the array (m + 1, n) and initiates further dividing of these two arrays, so that it calls itself again and forwards as a parameter the original array , starting and ending position of both arrays.
Next performs merging smaller subarrays made in previous recursions.

In the following figure you can see the start and end position, left and right array:

Deviding an array into smaller subarray

Merge sort algorithm. Dividing an array into smaller subarray

Figure 2: Merge sort. Dividing an array into smaller subarray

Figure 2 shows the initial division of the array into smaller subarrays.
In the next iteration, the initial array will be divided into two arrays when that iteration is completely completed, and this will only be achieved when all subsequently called iterations are completed. The division of the array looks like the following figure:

Figure 3: Merge-sort. Dividing into smaller arrays

As illustrated in Figure 3, the array is further divided until elementary arrays are achieved.

The function which divide arrays recursively:

void mergeSort(int a[], int l,int r,int n)
{

int m=(l+r)/2;
if(l < r)
{

mergeSort(a, l, m, n); //the left half of a given array
mergeSort(a, m+1, r, n); //the right half of a given array
mergeArrays(a, l, m, r, n); /* Merge left and right arrays. Returning from recursion the sorted subarrays are merged already */

}
return;

}

The recursive deviding process could be illustrated by:

Figure 3: Merge-sort. Dividing into smaller arrays. IV and V iteration

Figure 4: Merge-sort. Dividing into smaller arrays. IV and V iteration

As seen in Figure 4, each division results in subarrays that are independently sorted and then merged.

MergeSort function:

Figure 5: Merge-sort. Dividing into smaller arrays. Function mergeSort

Figure 4: Merge-sort. Dividing into smaller arrays. Function - execution

Figure 6: Merge-sort. Dividing into smaller arrays. Function - execution

When the division of arrays into elementary ones is completed, the elementary arrays are merged into larger arrays and the same are sorted:

Merge sorting. Merging smaller into larger arrays-scheme

Figure 7: Merge - sort. Merging smaller into larger arrays-scheme

Consider the merging process in the 3rd iteration shown in green in the previous figure. Iterations are now counted from the bottom up. Consider two arrays: {3, 5, 10} and {-34, 16}.
After merging you will get: {-34, 3, 5, 10, 16}
Function that does this:

void mergeArrays(int a[ ], int l, int m, int r, int n)
{

int k, i, j;
int aCopy[n];
for(int i=0; i < n; i++)
{

aCopy[i]=a[i];

}

The original array a[] is passed as a parameter, as well as the corresponding positions: left l, right r and middle m, as well as the dimension of the array n

void mergeArrays(int a[ ], int l, int m, int r, int n)
{

int k, i, j;
// Step 1: Create a temporary copy of the original array
int aCopy[ n ];
for(int i=0; i < n; i++)
{

aCopy[ i ]=a[ i ];// Copy each element from 'a' to 'aCopy'

}
// Step 2: Initialize pointers for merging process

for( i=k=l,j=m+1;i<=m && j<=d;k++){

// Step 3: Compare elements from the left and right subarrays
if(aCopy[ j ] < aCopy[ i ]){

a[ k ]=aCopy[ j ]; // Place the smaller element into the sorted array
j++;// Move the pointer of the right subarray

}
else{

a[ k ]=aCopy[ i ];// Place the smaller element into the sorted array
i++;// Move the pointer of the left subarray

}

// Step 4: Copy any remaining elements from the left subarray
for( ;i<=m; i++;k++){

a[k] = aCopy[i];

}
// Step 5: If there are any remaining elements in the right subarray,
// they are already in place, so no need for an additional loop.

}

Temporary Copy (aCopy) Creation:
- The original array a[] is copied into a temporary array aCopy[] to preserve the original values while performing the merge.
Pointer Initialization:
- i starts at the beginning of the left subarray (l).
- j starts at the beginning of the right subarray (m + 1).
- k is the index for the merged array, starting at l.
Merging with a Single for Loop:
- The for loop simultaneously compares elements from the left and right subarrays.
- If the current element in the right subarray (aCopy[j]) is smaller, it is placed in the merged array at position k.
- Otherwise, the element from the left subarray (aCopy[i]) is placed in the merged array.
- Pointers i, j, and k are adjusted accordingly.
Handling Remaining Elements:
- After the loop, if any elements remain in the left subarray, they are copied into the merged array.
- There's no need to copy remaining elements from the right subarray, as they are already in place.

A smaller value overrides the original array a [ ] at its current position "k":

Figure 8: Sorting by merging. Merging smaller into larger arrays-function

Moves the current position of the part of the copy whose value has been overridden at the original array, as well as the current position of the original array:

Figure 9: Sorting by merging. Merging smaller into larger arrays-functions-continued

Using the loop, we compare the value at the current position of the left array inside the copy with values at the current position of the right-hand side of the array copy:

Figure 10: Sorting by merging. Merging smaller into larger arrays-functions- continued 2

The next, we copy the remaining elements, if it has any

Figure 11: Sorting by merging. Merging smaller into larger arrays - function - continue moving

Figure 12: Sorting by merging. Merging smaller into larger arrays-functions-moving continue , schema

If some members of the array on the right are smaller than the members of the array on the left, they will be replaced
Let's look main part of application!

Main part of application

In the main part of the program, you need to specify and allocated a memory for an array, call the method of dividing the array, which further initiates a recursive procedure. when it is finished, the array will be sorted and after that it remains to display it on the screen:

#include < stdio.h >
void printArray(int a[], int n){

for(int i = 0; i < n; i++)

printf("%d ",a[ i ]);

printf("\n");

}

int main()
{

int n;
int a[ ]={ 5, 3, 10, -34, 16, 4, 24, 11, -12, 14};
n = sizeof(a) / sizeof(a[ 0 ]);

mergeSort(a, 0, n-1, n);
printArray(a, n);
return 0;

}

This method is significantly faster than bubble sorting because the execution time is linear - logarithmic T (n) = (n * log (n)) as opposed to bubble sorting whose extraction time is square

T(n)=n²

Detailed Example Walkthrough

To thoroughly demonstrate the Merge Sort algorithm's robustness, we'll walk through a more complex example using the array:
{12, 11, 13, 5, 6, 7}.
This will show how the array is recursively divided and then merged back together in sorted order.
Step 1: Initial ArrayThe array to be sorted is: {12, 11, 13, 5, 6, 7}.
Step 2: Divide the ArrayThe array is divided into two halves:

Left subarray: {12, 11, 13}
Right subarray: {5, 6, 7}

Step 3: Recursively Divide the Left Subarray

Divide {12, 11, 13} into:
- {12, 11} (left)
- {13} (right)
Further divide {12, 11} into:
- {12} (left)
- {11} (right)
At this point, each subarray contains only one element, so the recursion stops.

Step 4: Merge the Left Subarray

Merge {12} and {11}:
- Compare 12 and 11. Since 11 < 12, the merged array becomes {11, 12}.
Now, merge {11, 12} with {13}:
- Compare 11 with 13. Since 11 < 13, the merged array starts as {11}.
- Next, compare 12 with 13. Since 12 < 13, add 12 to the merged array: {11, 12}.
- Finally, add 13: the merged array is now {11, 12, 13}.

Step 5: Recursively Divide the Right Subarray

Divide {5, 6, 7} into:
- {5, 6} (left)
- {7} (right)
Further divide {5, 6} into:
- {5} (left)
- {6} (right)
Each subarray now contains one element, so the recursion stops.

Step 6: Merge the Right Subarray

Merge {5} and {6}:
- Compare 5 and 6. Since 5 < 6, the merged array becomes {5, 6}.
Now, merge {5, 6} with {7}:
- Compare 5 with 7. Since 5 < 7, the merged array starts as {5}.
- Next, compare 6 with 7. Since 6 < 7, add 6 to the merged array: {5, 6}.
- Finally, add 7: the merged array is now {5, 6, 7}.

Step 7: Merge the Two Halves

Now, merge {11, 12, 13} with {5, 6, 7}:
- Compare 11 with 5. Since 5 < 11, the merged array starts as {5}.
- Compare 11 with 6. Since 6 < 11, add 6: {5, 6}.
- Compare 11 with 7. Since 7 < 11, add 7: {5, 6, 7}.
- Now, add the remaining elements from the left subarray: {11, 12, 13}.
- The final sorted array is: {5, 6, 7, 11, 12, 13}.

Performance AnalysisTime Complexity:

Best Case: O(n log n) – The best-case scenario occurs when the array is already sorted, but the recursive splitting and merging still occur, leading to the same time complexity as the average and worst cases.
Average Case: O(n log n) – On average, the Merge Sort will divide the array into subarrays and merge them back together in O(n log n) time.
Worst Case: O(n log n) – Even in the worst case (e.g., when the array is sorted in reverse order), the time complexity remains O(n log n) because the algorithm always divides the array into two halves and requires logarithmic levels of merging.

Comparison with Other Sorting Algorithms:

Quick Sort: Quick Sort generally has better performance in practice due to less overhead in the recursive calls, with an average-case time complexity of O(n log n). However, its worst-case time complexity can degrade to O(n^2) if the pivot selection is poor.
Heap Sort: Like Merge Sort, Heap Sort also has a time complexity of O(n log n) in the best, average, and worst cases. However, Heap Sort is not a stable sort, which may make Merge Sort preferable in scenarios where stability is required.
Bubble Sort, Insertion Sort: Both of these algorithms have a time complexity of O(n^2) in the worst and average cases, making them inefficient for large datasets compared to Merge Sort.

Space Complexity:

Merge Sort requires additional space of O(n) for the temporary arrays used during the merging process. This is a disadvantage compared to in-place sorting algorithms like Quick Sort or Heap Sort, which require O(1) additional space. However, the stability and predictable performance of Merge Sort often outweigh this drawback, especially in situations where stability is crucial.

This detailed walkthrough and performance analysis should provide a deeper understanding of the Merge Sort algorithm and its advantages over other sorting methods.

Conclusion

In conclusion, Merge Sort stands out as an efficient and stable sorting algorithm that guarantees a time complexity of O(n log n) across all cases—best, average, and worst. Its stability makes it particularly useful in applications where maintaining the relative order of equal elements is essential. Although Merge Sort requires additional space due to the temporary arrays used in merging, its predictable performance and ability to handle large datasets efficiently make it an excellent choice for various scenarios, especially when working with external sorting, where the data may not fit entirely in memory.
Merge Sort is often chosen for sorting large datasets because it consistently performs well, regardless of the initial order of the elements. Its divide-and-conquer approach, which breaks down a complex problem into simpler subproblems, exemplifies how algorithmic design can significantly improve computational efficiency. While it may not always be the fastest in practice compared to Quick Sort, its stability and guaranteed O(n log n) performance make it a reliable choice for many sorting tasks.

Additional Resources

For those interested in further exploring the Merge Sort algorithm, the following resources can provide more in-depth explanations and opportunities for hands-on practice:

Tutorials:
- GeeksforGeeks Merge Sort Tutorial - A comprehensive tutorial with code examples and detailed explanations.
- Merge Sort Video Tutorial - A step-by-step video walkthrough of the Merge Sort algorithm.
Academic Papers:
- "The Design and Analysis of Computer Algorithms" by Aho, Hopcroft, and Ullman - A foundational text that covers the theory behind sorting algorithms, including Merge Sort.
- "Algorithms" by Robert Sedgewick and Kevin Wayne - This book provides an in-depth analysis of various sorting algorithms, including performance comparisons and real-world applications.
Practice Problems:
- LeetCode - Sort an Array - Practice implementing the Merge Sort algorithm by solving this problem.
- HackerRank - Merge Sort Counting Inversions - A more challenging problem that involves counting inversions using Merge Sort.

Sorting Array