Confusion passing an array by reference in recursive sort algorithm

Question

I'm confused about passing arrays by reference. Since arrays are stored on the heap it was my belief that when they are passed as parameters the value of the parameter is the location in the heap. This might be confusion as to what the variable is representing.

If the array is stored on the heap, what exactly does the ref keyword mean when passing an array to a method? It was my belief that changing the array in the called method would change the calling method since it was passed by value and the value contains a reference to the array.
If I skip Sort and instead call DoSort directly then unsortedArray is sorted correctly. In the program below, why is unsortedArray never sorted at the end of execution? Does this have anything to do with the fact that this is a recursive algorithm?

Here is the code:

public class Program {
    static void Main(string[] args) {
        int[] unsortedArray = new[] { 9, 7, 5, 3, 1 };
        Sort(unsortedArray);
    }

    public static void Sort(int[] sortArray) {
        DoSort(ref sortArray);
    }

    public static void DoSort(ref int[] doSortArray) {
        if (doSortArray.Length == 1) {
            return;
        }
        int midpoint = doSortArray.Length / 2;

        // divide the array into the left portion
        int[] left = new int[midpoint];
        for (int i = 0; i < midpoint; i++) {
            left[i] = doSortArray[i];
        }

        // divide the array into the right portion 
        int[] right = new int[doSortArray.Length - midpoint];
        int j = 0;
        for (int i = midpoint; i < doSortArray.Length; i++) {
            right[j] = doSortArray[i];
            j++;
        }

        DoSort(ref left);
        DoSort(ref right);

        doSortArray = Merge(left, right);
    }

    /// <summary>
    /// Merges the specified unmerged array.
    /// </summary>
    /// <param name="left">The left.</param>
    /// <param name="right">The right.</param>
    private static int[] Merge(int[] left, int[] right) {
        int i = 0;
        int[] result = new int[left.Length + right.Length];

        int leftIndex = 0;
        int rightIndex = 0;
        while (leftIndex < left.Length || rightIndex < right.Length) {
            if (leftIndex < left.Length && rightIndex < right.Length) {
                if (left[leftIndex] <= right[rightIndex]) {
                    result[i] = left[leftIndex];
                    leftIndex++;
                } else {
                    result[i] = right[rightIndex];
                    rightIndex++;
                }
            }
            else if (leftIndex < left.Length) {
                result[i] = left[leftIndex];
                leftIndex++;
            }
            else if (rightIndex < right.Length) {
                result[i] = right[rightIndex];
                rightIndex++;
            }
            i++;
        }

        return result;
    }
}

Passing Arrays as Arguments (C# Programming Guide)

Have a look at the link included in the top answer to this question. http://stackoverflow.com/questions/1981916/c-sharp-ref-keyword-usage — Daniel Brückner, Dec 13 '12 at 21:23
You're not passing `sortArray` by reference to `Sort`, only to `DoSort`. That's why it works correctly when bypassing `Sort`. — Dave Zych, Dec 13 '12 at 21:23
This seems converted from some other language. It is a very inefficient way to sort an array (splitting and merging where in-place seems to be the goal) . Just dump it. — H H, Dec 13 '12 at 21:24
@Henk - it's just a textbook example of MergeSort. I was more curious about the parameter passing than the performance. This would not go into production code! Thanks for the consideration. — Ian R. O'Brien, Dec 13 '12 at 21:27

score 2 · Accepted Answer · answered Dec 13 '12 at 21:22

Here's the difference:

int[] array = null;
DoSort(array)
//array is still null

DoSort(int[] array)
{
 array = new int[10];
}

...

int[] array = null;
DoSort(ref array)
//array is new int[10]

DoSort(ref int[] array)
{
 array = new int[10];
}

In either case, you can change the content of the array. Only when passed by reference can you change the actual value of the reference in the caller.

Your example needs ref because of this line

doSortArray = Merge(left, right);

Confusion passing an array by reference in recursive sort algorithm

1 Answers1