I have a basic question regarding scope in C: why does the following code from geeksforgeeks work? My info is: variable calls are call by value, i.e. anything that happens to say, the array arr inside a function does not translate to the outside.

/* C program for Merge Sort */
#include <stdio.h>
#include <stdlib.h>
 
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m 1..r]
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l   1;
    int n2 = r - m;
 
    /* create temp arrays */
    int L[n1], R[n2];
 
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i  )
        L[i] = arr[l   i];
    for (j = 0; j < n2; j  )
        R[j] = arr[m   1   j];
 
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i  ;
        }
        else {
            arr[k] = R[j];
            j  ;
        }
        k  ;
    }
 
    /* Copy the remaining elements of L[], if there
    are any */
    while (i < n1) {
        arr[k] = L[i];
        i  ;
        k  ;
    }
 
    /* Copy the remaining elements of R[], if there
    are any */
    while (j < n2) {
        arr[k] = R[j];
        j  ;
        k  ;
    }
}
 
/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        // Same as (l r)/2, but avoids overflow for
        // large l and h
        int m = l   (r - l) / 2;
 
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m   1, r);
 
        merge(arr, l, m, r);
    }
}
 
/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
    int i;
    for (i = 0; i < size; i  )
        printf("%d ", A[i]);
    printf("\n");
}
 
/* Driver code */
int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
 
    printf("Given array is \n");
    printArray(arr, arr_size);
 
    mergeSort(arr, 0, arr_size - 1);
 
    printf("\nSorted array is \n");
    printArray(arr, arr_size);
    return 0;
}

To be more concrete: why don't I have to declare arr globally for this to work? How come the last print call gives me the correct array?

CodePudding user response：

As an argument, the declaration int arr[] is really exactly the same as int *arr. You don't copy the array itself when calling the function.

The "value" that is passed is the pointer value itself (where the pointer is pointing).

CodePudding user response：

When an array is used in expressions it is with rare exception is implicitly converted to pointer to its first element.

On the other hand, the compiler adjusts a function parameter having an array type to pointer to the array element type. That is this function declaration

void merge(int arr[], int l, int m, int r);

is equivalent to

void merge(int *arr, int l, int m, int r);

Thus all elements of the passed array are passed by reference.

In C passing by reference means passing an object indirectly through a pointer to it.

So using the pointer arithmetic and a pointer to teh first element of an array you can access and change all original elements of the passed array.

Pay attention to that the subscript operator as for example arr[i] is calculated like *( arr i ).

Pay attention to that using a global array when functions depend on the global array is a bad practice. In such a case the functions can not be called with different array of different sizes.

CodePudding user response：

Arrays are not passed by value (in C, arrays are not first class objects, e.g. you can't assign to arrays, only to elements of an array; you can't return arrays from functions).

Instead, a pointer to the first element is passed by value. This allows the callee to modify elements of the array. This automatic rewrite of an array expression is sometimes described as an array decays to a pointer to its first element.

Any decent book on C should have a section explaining this special behavior of arrays in expressions.

The corresponding reference from the ISO C99 Standard is in 6.3.2.1#3 Lvalues, arrays, and function designators:

3 Except when it is the operand of the sizeof operator or the unary & operator, or is a string literal used to initialize an array, an expression that has type ‘‘array of type’’ is converted to an expression with type ‘‘pointer to type’’ that points to the initial element of the array object and is not an lvalue. If the array object has register storage class, the behavior is undefined