Why is reference-type parameter passed to function by reference implicitly in C#?

Question

So I was learning the Heapsort algorithms and I understood it perfectly. However, when looking at my code I do not actually understand why it works, since in C# if I want to change a value of a parameter by passing it to a function I have to use the ref keyword, otherwise its a value-type parameter which should not change when passed to a function.

public static class HeapSort
{
    public static List<int> Sort(List<int> array)
    {
        List<int> result = new List<int>();
        int n = array.Count;

        for(int i = n/2 - 1; i >= 0; i--)
        {
            Heapify(array, n, i);
        }

        int sizeOfArray = n;
        while(result.Count != n)
        {
            result.Insert(0, array[0]);
            array[0] = array[sizeOfArray - 1];
            array.RemoveAt(sizeOfArray - 1);
            sizeOfArray--;
            Heapify(array, sizeOfArray, 0);
        }

        return result;
    }

    private static void Heapify(List<int> array, int n, int i)
    {
        int smallest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if(left < n && array[smallest] > array[left])
        {
            smallest = left;
        }

        if(right < n && array[smallest] > array[right])
        {
            smallest = right;
        }

        if(smallest != i)
        {
            int temp = array[smallest];
            array[smallest] = array[i];
            array[i] = temp;
            Heapify(array, n, smallest);
        }

    }
}

I don't understand why calling Heapify without ref works in changing the array.

Answer 1

In c# there are reference types and value types. Value types are passed by value unless you pass them with ref keyword. Reference types are always passed by reference.

For example if you declare two variables like this

List<int> myList = new List<int>();
int myint = 0;

myInt holds value 0, but myList only holds a reference which points to actual instance of List<int>. This means that when you pass myInt to a method you just pass a copy of it's value. When you pass myList you do the same thing - you pass a copy of its value, but its value is a reference to instance of List<int>, so copy of this reference still refers to the same List<int> on the heap.

When you pass variable with a ref keyword you actually pass a pointer to your original variable. If you pass myInt with ref keyword your method will receive pointer to myInt, so it will be able to modify its actual value. If you pass myList with ref keyword same thing happens. Now your method can modify actual value of myList variable. It can set it to some other reference.

It's probably easier to understand when you see it in practice, so here is small console application showing difference between two methods which differ only by use of ref keyword

static void Main(string[] args)
{
    //create new instane of List<int> on the heap and store reference to it on the stack in 'myList 'variable
    List<int> myList = new List<int>() { 1 };
    //create new instance of int and store it on the stack in 'myInt' variable
    int myint = 2;

    //call MyMethod
    //copy value of myInt (2) to the new stack frame and store it in 'i' variable
    //copy value of myList (reference to List<int>) to the new stack frame and store it in 'list' variable
    MyMethod(myint, myList);
    Console.WriteLine(myint);       //prints 2
    Console.WriteLine(myList[0]);   //prints 4

    //call MyMethod
    //inside new stack frame store pointer to 'myint' variable
    //inside new stack frame store pointer to 'myList' variable
    MyMethod(ref myint, ref myList);
    Console.WriteLine(myint);       //prints 3
    Console.WriteLine(myList[0]);   //prints 5

    Console.ReadLine();
}

static void MyMethod(int i, List<int> list)
{
    //store value of 3 on stack in variable 'i'
    i = 3;
    //use reference stored on stack in 'list' variable to find our instance of List<int> on the heap and store 4 under index 0
    list[0] = 4;
    //create new instane of List<int> on the heap and store reference to it on the stack, in 'list 'variable
    list = new List<int>() { 5 };
}

static void MyMethod(ref int i, ref List<int> list)
{
    //use pointer to 'myInt' variable to store value of 3 in 'myInt' variable
    i = 3;
    //use pointer to 'myList' variable to get reference stored in it and use that reference to find our instance of List<int> on the heap and store 4 under index 0
    list[0] = 4;
    //create new instane of List<int> on the heap and use pointer to 'myList' variable to store reference to that new instance inside 'myList' variable
    list = new List<int>() { 5 };
}