Choose your language!

---

|

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

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:

C and C++

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 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 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:

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:

C and C++

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

C and C++

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<=r;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:

C

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

}

C++

#include < iostream >

using namespace std;

void printArray(int a[], int n){

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

cout << a[i] << endl;

cout << endl;

}

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²

Complete solution in C++

#include <iostream>

using namespace std;

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<=r; 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.
}

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


void printArray(int a[], int n)
{
    for(int i = 0; i < n; i++)
        cout << a[i] << endl;
    cout << endl;
}

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

Merge Sort in C++ (with detailed explanations)

This program implements the Merge Sort algorithm, one of the most well-known sorting algorithms based on the divide and conquer paradigm.

The algorithm works as follows:

• the array is recursively divided into two approximately equal parts,
• the left and right subarrays are sorted independently,
• the two sorted subarrays are then merged into a single sorted array.

---

mergeArrays function – merging two sorted subarrays

The function mergeArrays receives the following parameters:

• a[] – the original array,
• l – left index of the segment being merged,
• m – middle index (end of the left subarray),
• r – right index of the segment,
• n – total length of the array.

The goal is to merge two already sorted subarrays: [l ... m] and [m+1 ... r] into a single sorted segment.

#include <iostream>
using namespace std;

void mergeArrays(int a[], int l, int m, int r, int n)
{
    int k, i, j;

    // STEP 1: Create a temporary copy of the array
    // Note: the entire array is copied, which is not optimal
    int aCopy[n];
    for (int i = 0; i < n; i++)
    {
        aCopy[i] = a[i];
    }

    // STEP 2: Initialize indices
    // i -> left subarray
    // j -> right subarray
    // k -> position in the original array
    for (i = k = l, j = m + 1; i <= m && j <= r; k++)
    {
        // STEP 3: Compare elements from left and right subarrays
        if (aCopy[j] < aCopy[i])
        {
            a[k] = aCopy[j];
            j++;
        }
        else
        {
            a[k] = aCopy[i];
            i++;
        }
    }

    // STEP 4: Copy remaining elements from the left subarray
    for (; i <= m; i++, k++)
    {
        a[k] = aCopy[i];
    }

    // Remaining elements from the right subarray
    // are already in correct positions
}

Important note: This implementation is correct but inefficient because it copies the entire array into a temporary buffer, even though only the segment [l ... r] needs to be merged.

---

mergeSort function – recursive array division

The mergeSort function recursively divides the array until each subarray contains only one element, which is trivially sorted.

void mergeSort(int a[], int l, int r, int n)
{
    if (l < r)
    {
        int m = (l + r) / 2;

        // Sort the left half
        mergeSort(a, l, m, n);

        // Sort the right half
        mergeSort(a, m + 1, r, n);

        // Merge the sorted halves
        mergeArrays(a, l, m, r, n);
    }
}

The recursion stops when l == r, because a segment with a single element is already sorted.

---

Time and space complexity

• Time complexity: O(n log n) in the best, average, and worst case.
• Space complexity: O(n) due to the use of an auxiliary array.

Because of its stable time complexity, Merge Sort is well suited for large datasets, but it requires additional memory.

---

Where this code can be improved

• The parameter n should not be passed through every recursive call.
• The auxiliary array should not be created inside each merge operation.
• Only the segment [l ... r] should be copied, not the entire array.

---

Guidelines for a more optimal implementation

A more efficient approach is to:

• create a single auxiliary array with the same size as the original array,
• pass it through recursive calls,
• copy only the portion of the array that is currently being merged.

// Conceptual outline of an optimized approach
void merge(int a[], int temp[], int l, int m, int r);
void mergeSort(int a[], int temp[], int l, int r);

This avoids repeated memory allocation and makes the algorithm significantly more efficient in practice.

After starting the program:

Figure 13: Merge sort example-running the application

Optimized Merge Sort in C++ (production-style implementation)

Below is an optimized version of the Merge Sort algorithm, written in a way that is commonly used in real-world and textbook implementations. The main improvement compared to the basic version is the use of a single auxiliary array, which significantly reduces memory overhead.

---

Main optimization ideas

• Only one temporary array is allocated.
• The temporary array is reused throughout the recursion.
• Only the segment [l ... r] is copied during merging.
• No unnecessary parameters are passed through recursive calls.

---

Optimized implementation

#include <iostream>
using namespace std;

// Merges two sorted subarrays:
// a[l..m] and a[m+1..r]
void merge(int a[], int temp[], int l, int m, int r)
{
    // Copy only the relevant segment into the temporary array
    for (int i = l; i <= r; i++)
        temp[i] = a[i];

    int i = l;      // pointer for left subarray
    int j = m + 1;  // pointer for right subarray
    int k = l;      // pointer for merged array

    // Merge elements back into the original array
    while (i <= m && j <= r)
    {
        if (temp[i] <= temp[j])
            a[k++] = temp[i++];
        else
            a[k++] = temp[j++];
    }

    // Copy remaining elements from the left subarray
    while (i <= m)
        a[k++] = temp[i++];

    // Remaining elements from the right subarray
    // are already in correct positions
}

// Recursive Merge Sort
void mergeSort(int a[], int temp[], int l, int r)
{
    if (l < r)
    {
        int m = l + (r - l) / 2;

        mergeSort(a, temp, l, m);       // sort left half
        mergeSort(a, temp, m + 1, r);   // sort right half
        merge(a, temp, l, m, r);        // merge halves
    }
}

// Utility function to print the array
void printArray(int a[], int n)
{
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;
}

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

    int temp[n]; // single auxiliary array

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

    return 0;
}

---

Why this version is better

• Memory-efficient: only one auxiliary array of size n.
• Faster in practice: avoids repeated allocation and full-array copying.
• Clean recursion: no unnecessary parameters.
• Stable sorting: equal elements preserve their relative order.

---

Time and space complexity

• Time complexity: O(n log n) in all cases.
• Space complexity: O(n) due to the auxiliary array.

This makes Merge Sort a very reliable algorithm for large datasets, especially when predictable performance is required.

---

Further improvements (advanced topics)

• Switch to Insertion Sort for very small subarrays.
• Use iterative (bottom-up) Merge Sort to avoid recursion.
• Apply Merge Sort to linked lists where it becomes an in-place algorithm.

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