Heapsort with min-heap not working correctly

Question

I'm trying to implement heapsort with min-heap. Input is array of positive integers and array's zero index stores the size. Can anyone spot my error? Language used here is C#. The algorithm works correctly sometimes, but with bigger arrays the root is not the smallest value in the array.

    static void CreateMinHeap(int[] input)
    {
        input[0] = input.Length - 1;

        for (int i = (input[0] / 2); i > 0; i--)
        {
            MinHeapify(input, i);
        }
    }

    static void MinHeapify(int[] input, int index)
    {
        var left = 2 * index;
        var right = 2 * index + 1;
        int smallest;

        if (left < input.Length && input[left] < input[index])
            smallest = left;
        else
            smallest = index;

        if (right < input.Length && input[right] < input[smallest])
            smallest = right;

        if (smallest != index)
        {
            Swap(ref input[smallest], ref input[index]);
            MinHeapify(input, smallest);
        }
    }

    static public void HeapSort(int[] input)
    {
        CreateMinHeap(input);

        for (int i = input[0]; i > 0; i--)
        {
            Swap(ref input[1], ref input[i]);
            input[0]--;
            MinHeapify(input, 1);
        }
    }

    static public void Swap(ref int a, ref int b)
    {
        var temp = a;
        a = b;
        b = temp;
    }

Answer 1

Background

As far as I understand you are using your array in two partitions.

The first partition contains the heap, and the second partition (which starts empty) contains the sorted values.

During HeapSort the size of the first partition decreases, and the second increases until you have a sorted array.

Bug

The problem is that when you run MinHeapify you have not told it that the length of the heap has decreased so it is trying to heapify some of your sorted nodes.

Fix

You are keeping track of the size of the heap in entry input[0] so this should be easy to fix.

Try changing:

    if (left < input.Length && input[left] < input[index])
        smallest = left;
    else
        smallest = index;

    if (right < input.Length && input[right] < input[smallest])
        smallest = right;

to

    if (left <= input[0] && input[left] < input[index])
        smallest = left;
    else
        smallest = index;

    if (right <= input[0] && input[right] < input[smallest])
        smallest = right;