Swimburger

Generic Merge Sort in C# .NET

Niels Swimberghe

Niels Swimberghe - - .NET

Follow me on Twitter, buy me a coffee

Early this year, I decided to brush up on my algorithms and data structure knowledge. I took these great two courses (1, 2) on PluralSight by Robert Horvick.
To practice what I learned in this course, I decided to create generic versions of the different algorithms and data structures.

What do I mean by generic versions? These types of courses always use integers or strings to demonstrate the algorithms. Instead of using those primitive data types, I'm reimplementing the algorithms and data structures using C#'s generic type parameters.

Here's a console application with a generic method MergeSort to perform a merge sort on an enumerable:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var randomNumbers = new int[] { 5, 4, 5, 7, 6, 9, 4, 1, 1, 3, 4, 50, 56, 41 };

        var sortedNumbers = MergeSort(randomNumbers.AsEnumerable());
        Console.WriteLine("Merge Sort:");
        PrintList(sortedNumbers);
        Console.ReadKey();
        Console.Clear();
    }

    private static IEnumerable<T> MergeSort<T>(IEnumerable<T> list) where T : IComparable<T>
    {
        T[] items = list.ToArray();
        return InternalMergeSort(items);
    }

    private static T[] InternalMergeSort<T>(T[] items) where T : IComparable<T>
    {
        int listLength = items.Length;

        if (listLength == 1)
        {
            return items;
        }

        int median = listLength / 2;

        T[] left = new T[median];
        T[] right = new T[listLength - median];
        Array.Copy(items, left, left.Length);
        Array.Copy(items, median, right, 0, right.Length);

        InternalMergeSort(left);
        InternalMergeSort(right);

        return Merge(items, left, right);
    }

    private static T[] Merge<T>(T[] items, T[] left, T[] right) where T : IComparable<T>
    {
        int leftIndex = 0;
        int rightIndex = 0;

        int leftLength = left.Length;
        int rightLength = right.Length;
        int totalItems = leftLength + rightLength;

        for (int targetIndex = 0; targetIndex < totalItems; targetIndex++)
        {
            if(leftIndex >= leftLength)
            {
                items[targetIndex] = right[rightIndex];
                rightIndex++;
            }
            else if(rightIndex >= right.Length)
            {
                items[targetIndex] = left[leftIndex];
                leftIndex++;
            }
            else if(left[leftIndex].CompareTo(right[rightIndex]) < 0)
            {
                items[targetIndex] = left[leftIndex];
                leftIndex++;
            }
            else
            {
                items[targetIndex] = right[rightIndex];
                rightIndex++;
            }
        }

        return items;
    }

    private static void PrintList<T>(IEnumerable<T> list)
    {
        foreach (var item in list)
        {
            Console.WriteLine(item);
        }
    }
}

By using a generic type parameter with the constraint that the type has to implement the IComparable<T> (or IComparable) interface, you can perform the merge sort algorithm without knowing the exact type you are working with.

If you want to understand the logic behind the merge sort algorithm, I recommend checking out the courses mentioned earlier. There's also a lot of other great resources out there online!

Disclaimer: This code works, but is only developed for the sake of practice. Use at your own risk or just use a sorting library. If you see some room for improvement, there most likely is, I'm all ears~

Related Posts

Related Posts

.NET bot writing on whitebpard

Generic Insertion Sort in C# .NET

- .NET
To practice algorithms and data structures, I reimplemented insertion sort using C#'s generic type parameters.
.NET bot writing on whitebpard

Generic Bubble Sort in C# .NET

- .NET
To practice algorithms and data structures, I reimplemented bubble sort using C#'s generic type parameters.
.NET bot writing on whitebpard

Generic Binary Search in C# .NET

- .NET
To practice algorithms and data structures, I reimplemented binary search using C#'s generic type parameters.
.NET bot writing on whitebpard

Generic Merge Sort in C# .NET

- .NET
To practice algorithms and data structures, I reimplemented merge sort using C#'s generic type parameters.
.NET bot writing on whitebpard

Generic Quick Sort in C# .NET

- .NET
To practice algorithms and data structures, I reimplemented Quick Sort using C#'s generic type parameters.
.NET bot writing on whitebpard

Generic Linear Search/Sequential Search for a sequence in C# .NET

- .NET
To practice algorithms and data structures, I reimplemented Linear Search/Sequential Search for a sequence using C#'s generic type parameters.
.NET bot writing on whitebpard

Generic Boyer–Moore–Horspool algorithm in C# .NET

- .NET
To practice algorithms and data structures, I reimplemented Boyer–Moore–Horspool algorithm for a sequence using C#'s generic type parameters.
.NET Bot, Azure, and Discord are together in a Discord server

How to create a Discord Bot using the .NET worker template and host it on Azure Container Instances

- Azure
Learn how to develop a Discord bot using the .NET worker template, containerize it using Docker, push the container image to Azure Container Registry, and host it on Azure Container Instances.