C# Example 3

using System;
using System.Collections.Generic;
using System.Diagnostics;

// Kaizer here. I implemented and compared different sorting algorithms using 3 main ones. quicksort, mergesort, and heapsort, in terms of performance.
class Program
{
    // function to print an array
    static void PrintArray(List<int> arr)
    {
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }

    // quicksort implementation
    static int Partition(List<int> arr, int low, int high)
    {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++)
        {
            if (arr[j] < pivot)
            {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp1 = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp1;
        return i + 1;
    }

    static void Quicksort(List<int> arr, int low, int high)
    {
        if (low < high)
        {
            int pi = Partition(arr, low, high);
            Quicksort(arr, low, pi - 1);
            Quicksort(arr, pi + 1, high);
        }
    }

    // mergesort implementation
    static void Merge(List<int> arr, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        List<int> L = new List<int>(n1);
        List<int> R = new List<int>(n2);

        for (int i = 0; i < n1; i++)
            L.Add(arr[left + i]);
        for (int j = 0; j < n2; j++)
            R.Add(arr[mid + 1 + j]);

        int i1 = 0, j1 = 0, k = left;
        while (i1 < n1 && j1 < n2)
        {
            if (L[i1] <= R[j1])
            {
                arr[k] = L[i1];
                i1++;
            }
            else
            {
                arr[k] = R[j1];
                j1++;
            }
            k++;
        }

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

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

    static void Mergesort(List<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);
        }
    }

    // heapsort implementation
    static void Heapify(List<int> arr, int n, int i)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest])
            largest = left;

        if (right < n && arr[right] > arr[largest])
            largest = right;

        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            Heapify(arr, n, largest);
        }
    }

    static void Heapsort(List<int> arr)
    {
        int n = arr.Count;
        for (int i = n / 2 - 1; i >= 0; i--)
            Heapify(arr, n, i);

        for (int i = n - 1; i > 0; i--)
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            Heapify(arr, i, 0);
        }
    }

    // function to measure and compare sorting times
    static void CompareSorts(List<int> arr)
    {
        List<int> arr1 = new List<int>(arr);
        List<int> arr2 = new List<int>(arr);
        List<int> arr3 = new List<int>(arr);

        Stopwatch stopwatch = new Stopwatch();

        stopwatch.Start();
        Quicksort(arr1, 0, arr1.Count - 1);
        stopwatch.Stop();
        Console.WriteLine($"Quicksort time: {stopwatch.Elapsed.TotalSeconds} seconds");

        stopwatch.Restart();
        Mergesort(arr2, 0, arr2.Count - 1);
        stopwatch.Stop();
        Console.WriteLine($"Mergesort time: {stopwatch.Elapsed.TotalSeconds} seconds");

        stopwatch.Restart();
        Heapsort(arr3);
        stopwatch.Stop();
        Console.WriteLine($"Heapsort time: {stopwatch.Elapsed.TotalSeconds} seconds");
    }

    static void Main(string[] args)
    {
        List<int> arr = new List<int> { 12, 11, 13, 5, 6, 7 };
        Console.Write("Original array: ");
        PrintArray(arr);

        CompareSorts(arr);
    }
}