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. stackoverflow.com/questions/1981916/c-sharp-ref-keyword-usage — Daniel Brückner
– Daniel Brückner, Commented Dec 13, 2012 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
– Dave Zych, Commented Dec 13, 2012 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. — Henk Holterman
– Henk Holterman, Commented Dec 13, 2012 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
– Ian R. O'Brien, Commented Dec 13, 2012 at 21:27

Erix · Accepted Answer · 2012-12-13 21:22:42Z

2

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);

answered Dec 13, 2012 at 21:22

Erix

7,1053 gold badges40 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Confusion passing an array by reference in recursive sort algorithm

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related