Merge Sort in C#: How It Works, Implementation, Time Complexity, and Practical Example

Introduction

Algorithms are a fundamental part of software development. They define the steps a program follows to solve a problem, process data, or produce a result.

In C#, algorithms are used in many areas, including data processing, searching, sorting, file processing, application development, and performance optimization.

One common example is Merge Sort, a divide-and-conquer sorting algorithm. Merge Sort is useful for understanding how a large problem can be divided into smaller problems, solved independently, and then combined to produce the final result.

In this article, we will understand how Merge Sort works, implement it in C#, walk through the implementation step by step, and examine its time and space complexity.

What Is an Algorithm?

An algorithm is a finite sequence of well-defined steps used to solve a particular problem.

For example, suppose we have the following array:

34, 7, 23, 32, 5, 62

If the requirement is to arrange these numbers in ascending order, we can use a sorting algorithm.

The expected result is:

5, 7, 23, 32, 34, 62

Different algorithms can solve the same problem, but they may differ in execution time, memory usage, and implementation complexity.

A good algorithm generally has the following characteristics:

Common Types of Algorithms in C#

C# developers work with many different algorithmic approaches.

Algorithm Category

Examples

Sorting

Bubble Sort, Merge Sort, Quick Sort

Searching

Linear Search, Binary Search

Graph

Dijkstra's Algorithm, A*

Dynamic Programming

Fibonacci, Knapsack

Greedy

Activity Selection

Backtracking

N-Queens, Sudoku Solver

The appropriate algorithm depends on the problem, input size, data structure, and performance requirements.

What Is Merge Sort?

Merge Sort is a divide-and-conquer sorting algorithm.

The basic idea is:

  1. Divide the array into two smaller arrays.

  2. Recursively sort each half.

  3. Merge the two sorted halves.

  4. Continue until the complete array is sorted.

For example, consider:

34, 7, 23, 32, 5, 62

The first division produces:

34, 7, 23
32, 5, 62

These arrays are divided again:

34, 7       23
32, 5       62

Eventually, individual elements are obtained:

34   7   23   32   5   62

Individual elements are already sorted by themselves. Merge Sort then combines them while maintaining sorted order.

The final result is:

5, 7, 23, 32, 34, 62

How Merge Sort Works

The algorithm has two important operations.

Divide

The input array is repeatedly divided into two halves until each part contains one element.

Conquer and Merge

The smaller arrays are sorted and merged together.

For example:

[34, 7]

is divided into:

[34]
[7]

When these two arrays are merged, the algorithm compares 34 and 7 and produces:

[7, 34]

The same process is repeated for the remaining portions of the original array.

Merge Sort Implementation in C#

The following example implements Merge Sort using integer arrays.

using System;

class MergeSortAlgorithm
{
    public static void MergeSort(int[] array)
    {
        if (array.Length <= 1)
            return;

        int mid = array.Length / 2;

        int[] left = new int[mid];
        int[] right = new int[array.Length - mid];

        // Copy elements into the left half
        for (int i = 0; i < mid; i++)
        {
            left[i] = array[i];
        }

        // Copy elements into the right half
        for (int i = mid; i < array.Length; i++)
        {
            right[i - mid] = array[i];
        }

        // Recursively sort both halves
        MergeSort(left);
        MergeSort(right);

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

    private static void Merge(
        int[] array,
        int[] left,
        int[] right)
    {
        int i = 0;
        int j = 0;
        int k = 0;

        // Compare elements from both arrays
        while (i < left.Length && j < right.Length)
        {
            if (left[i] <= right[j])
            {
                array[k++] = left[i++];
            }
            else
            {
                array[k++] = right[j++];
            }
        }

        // Copy remaining elements from left array
        while (i < left.Length)
        {
            array[k++] = left[i++];
        }

        // Copy remaining elements from right array
        while (j < right.Length)
        {
            array[k++] = right[j++];
        }
    }

    public static void PrintArray(int[] array)
    {
        Console.WriteLine(string.Join(", ", array));
    }

    static void Main()
    {
        int[] data = { 34, 7, 23, 32, 5, 62 };

        Console.WriteLine("Original Array:");
        PrintArray(data);

        MergeSort(data);

        Console.WriteLine("Sorted Array:");
        PrintArray(data);
    }
}

Step-by-Step Explanation

Step 1: Check the Array Size

The first condition is:

if (array.Length <= 1)
    return;

An array containing zero or one element is already sorted, so there is nothing to divide.

Step 2: Divide the Array

The middle position is calculated:

int mid = array.Length / 2;

Two arrays are then created:

int[] left = new int[mid];
int[] right = new int[array.Length - mid];

The original array is divided between these two arrays.

Step 3: Recursively Sort Both Halves

The algorithm calls itself for both arrays:

MergeSort(left);
MergeSort(right);

This continues until the arrays contain one element.

Step 4: Merge the Sorted Arrays

After both halves have been sorted, they are passed to the Merge method:

Merge(array, left, right);

The method compares the current element from each array and places the smaller element into the result.

For example:

Left:  [7, 34]
Right: [5, 23]

The comparison starts with:

7 vs 5

Since 5 is smaller, it is placed into the result.

The process continues until all elements have been copied.

Example Output

For the input:

34, 7, 23, 32, 5, 62

The program produces:

Original Array:
34, 7, 23, 32, 5, 62

Sorted Array:
5, 7, 23, 32, 34, 62

For the author's submission, a screenshot of the application running with this output should be added here. A screenshot from the author's own development environment would also satisfy the editor's request for a practical snapshot.

Merge Sort Time Complexity

Merge Sort has predictable time complexity.

Case

Time Complexity

Best Case

O(n log n)

Average Case

O(n log n)

Worst Case

O(n log n)

The array is divided into approximately log n levels, and each level requires approximately n operations to merge the elements.

Therefore:

O(n) × O(log n) = O(n log n)

Space Complexity

The implementation above creates additional arrays while dividing and merging the input.

Therefore, the auxiliary space complexity is:

O(n)

The recursive calls also use stack space.

Is Merge Sort Stable?

Yes. Merge Sort can be implemented as a stable sorting algorithm.

In the implementation above:

if (left[i] <= right[j])

the element from the left array is selected when two values are equal.

For objects containing multiple properties, this behavior can preserve the relative order of elements having equal sort keys, provided the implementation maintains that ordering.

Merge Sort vs Other Sorting Algorithms

Algorithm

Best Case

Average Case

Worst Case

Typical Extra Space

Bubble Sort

O(n)

O(n²)

O(n²)

O(1)

Merge Sort

O(n log n)

O(n log n)

O(n log n)

O(n)

Quick Sort

O(n log n)

O(n log n)

O(n²)

Depends on implementation

Insertion Sort

O(n)

O(n²)

O(n²)

O(1)

This comparison shows why algorithm selection matters. Merge Sort provides predictable O(n log n) performance, while some alternatives can have different worst-case behavior.

Real-World Example: Sorting Records

Consider an application that receives customer transaction records that need to be processed in ascending order of transaction amount.

A simplified model could look like this:

public class Transaction
{
    public int Id { get; set; }
    public decimal Amount { get; set; }
}

The sorting requirement could be represented as:

Transaction 101 - ₹750
Transaction 102 - ₹250
Transaction 103 - ₹1200
Transaction 104 - ₹500

The expected sorted order would be:

Transaction 102 - ₹250
Transaction 104 - ₹500
Transaction 101 - ₹750
Transaction 103 - ₹1200

In a real application, developers should also consider whether the built-in .NET sorting APIs are more appropriate than implementing Merge Sort manually.

The value of implementing Merge Sort is primarily educational and algorithmic: it helps developers understand divide-and-conquer techniques, recursion, merging, complexity analysis, and the trade-offs involved in sorting.

When Is Merge Sort Useful?

Merge Sort can be useful when predictable O(n log n) sorting performance is important.

Common scenarios include:

However, the best sorting approach depends on the application. In everyday C# development, the built-in .NET collection and LINQ sorting capabilities are often preferable because they are already implemented, tested, and integrated into the framework.

Common Mistakes When Implementing Merge Sort

Forgetting the Base Case

Without:

if (array.Length <= 1)
    return;

the recursive calls would not terminate correctly.

Incorrect Array Indexing

The merge operation needs to track three positions:

i → left array
j → right array
k → destination array

Incorrectly updating any of these indexes can result in missing or duplicated elements.

Forgetting Remaining Elements

After the main comparison loop finishes, one of the arrays may still contain elements.

Both remaining-element loops are therefore required:

while (i < left.Length)
{
    array[k++] = left[i++];
}

while (j < right.Length)
{
    array[k++] = right[j++];
}

Ignoring Space Requirements

Although Merge Sort provides predictable time complexity, this implementation requires additional memory for temporary arrays.

The memory trade-off should be considered when working with very large datasets.

Best Practices for Working With Algorithms in C#

When implementing or evaluating an algorithm in a C# application:

  1. Understand the problem before selecting an algorithm.

  2. Analyze both time and space complexity.

  3. Test with small and large inputs.

  4. Include edge cases such as empty arrays and single-element arrays.

  5. Compare a custom implementation with the appropriate .NET API.

  6. Measure performance when optimization is actually required.

  7. Keep algorithm-specific code separated from application logic.

  8. Add tests for expected, boundary, and invalid inputs.

Complete Source Code

For the C# Corner submission, the complete working project should be uploaded as a ZIP file along with the article.

The ZIP should ideally contain:

MergeSortDemo/
├── MergeSortDemo.csproj
├── Program.cs
└── README.md

The README.md file can briefly explain how to build and run the project.

This gives readers a reproducible example instead of requiring them to manually reconstruct the project from individual snippets.

Conclusion

Merge Sort is a useful example for understanding how divide-and-conquer algorithms work in C#. The algorithm repeatedly divides an array into smaller portions, sorts those portions, and merges them to produce the final sorted result.

Its best, average, and worst-case time complexity is O(n log n), while the implementation presented in this article uses O(n) auxiliary space.

More importantly, implementing an algorithm from scratch helps developers understand the trade-offs behind algorithm selection. In production C# applications, custom algorithms should be used when there is a clear requirement; otherwise, the appropriate built-in .NET functionality is often the simpler choice.

For the final C# Corner submission, adding the author's own observations, a screenshot of the program running, and a complete downloadable POC will make the article substantially more practical and address the editor's feedback.