Merge sort algorithm explained with c program.

Merge Sort Algorithm Explained for Beginners

When I first learned Merge Sort, I struggled to understand why we kept splitting arrays into smaller parts. But after practicing with examples, I realized that Merge Sort becomes very powerful because it breaks complex problems into smaller and easier tasks.

In this guide, I will explain Merge Sort in a simple and beginner-friendly way using diagrams, examples, and a complete C program. By the end of this article, you will clearly understand how Merge Sort works internally.

What is Merge Sort?

Merge Sort is a popular sorting algorithm based on the Divide and Conquer technique. Instead of sorting the entire array at once, Merge Sort divides the array into smaller parts, sorts them individually, and then merges them back together.

Merge Sort works by dividing the array repeatedly until each part contains only one element.

Real-Life Example of Merge Sort

Imagine you have a large stack of exam papers. Instead of sorting the whole stack at once, you divide the papers into smaller groups. Then you sort each group separately and combine them back together in order.

That is exactly how Merge Sort works.

Understanding Merge Sort Step by Step

Suppose we have the following array:

38, 27, 43, 3, 9, 82, 10

Step 1: Divide the Array

[38, 27, 43, 3, 9, 82, 10]

Split into:

[38, 27, 43]
[3, 9, 82, 10]

Step 2: Keep Dividing

[38, 27, 43]
→ [38] [27, 43]
→ [27] [43]

The process continues until each subarray contains only one element.

Step 3: Merge Sorted Arrays

[27] + [43]
→ [27, 43]

[38] + [27, 43]
→ [27, 38, 43]

Merge Sort Visualization

Original Array:

[8, 4, 2, 6]

Divide:
[8, 4] [2, 6]

Further Divide:
[8] [4] [2] [6]

Merge:
[4, 8] [2, 6]

Final Merge:
[2, 4, 6, 8]

Merge Sort Algorithm

mergeSort(array)
{
    divide the array into two halves

    mergeSort(left half)
    mergeSort(right half)

    merge the sorted halves
}
    

Merge Sort Program in C

Below is a complete Merge Sort implementation in C language.

#include 

void merge(int arr[], int left, int mid, int right)
{
    int i, j, k;

    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];

    for(i = 0; i < n1; i++)
        L[i] = arr[left + i];

    for(j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    i = 0;
    j = 0;
    k = left;

    while(i < n1 && j < n2)
    {
        if(L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }

        k++;
    }

    while(i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    while(j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right)
{
    if(left < right)
    {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

void printArray(int arr[], int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
}

int main()
{
    int arr[] = {38, 27, 43, 3, 9, 82, 10};

    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);

    printf("Sorted Array:\n");

    printArray(arr, n);

    return 0;
}
    

Output

3 9 10 27 38 43 82
    

Time Complexity of Merge Sort

Case	Complexity
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n log n)

Advantages of Merge Sort

• Consistent performance in all cases
• Efficient for large datasets
• Stable sorting algorithm
• Good for linked lists and external sorting

Disadvantages of Merge Sort

• Requires extra memory space
• Can be slower for small datasets

Merge Sort vs Quick Sort

Feature	Merge Sort	Quick Sort
Worst Case Complexity	O(n log n)	O(n²)
Memory Usage	Higher	Lower
Stable Sorting	Yes	No

Video Tutorial

Watch this beginner-friendly Merge Sort explanation video.

Frequently Asked Questions

Why is Merge Sort efficient?

Merge Sort divides the problem into smaller parts and sorts them efficiently using recursion.

What is the time complexity of Merge Sort?

Merge Sort has O(n log n) complexity in all cases.

What is merging in Merge Sort?

Merging means combining two sorted arrays into one sorted array.

Is Merge Sort better than Bubble Sort?

Yes. Merge Sort is significantly faster and more efficient for large datasets.

Final Thoughts

Merge Sort is one of the most reliable sorting algorithms in computer science. Even though recursion may seem difficult at first, practicing a few examples makes the concept much easier.

I recommend tracing the algorithm step by step on paper to understand how splitting and merging work internally.

About the Author

This article was written for beginner programmers who want simple and practical explanations of programming concepts.

Website: Bsccoding.online