Merge sort with pointer to pointer array not working

Question

Hello I've got this implementation of merge sort:

    void merge(Person **arr[], int firstElement, int midElement, int lastElement)
{
    int firstHalfSize = midElement - firstElement + 1;
    int secondHalfSize = lastElement - midElement;
    Person *firstHalfArray[firstHalfSize];
    Person *secondHalfArray[secondHalfSize];

    char *p;
    char *s;

    for (int i = 0; i < firstHalfSize; i++)
    {
        firstHalfArray[i] = *arr[firstElement + i];
    }

    for (int j = 0; j < secondHalfSize; j++)
    {
        secondHalfArray[j] = *arr[midElement + 1+ j];

    }

    int index1 = 0;
    int index2 = 0;
    int mergedArrIndex = firstElement;

    while (index1 < firstHalfSize && index2 < secondHalfSize)
    {

        if ((*firstHalfArray)[index1].id <= (*secondHalfArray)[index2].id)
        {
            arr[mergedArrIndex] = &firstHalfArray[index1];
            index1++;
        }
        else
        {
            arr[mergedArrIndex] = &secondHalfArray[index2];
            index2++;
        }
        mergedArrIndex++;
    }

    while (index1 < firstHalfSize)
    {
        arr[mergedArrIndex] = &firstHalfArray[index1];
        mergedArrIndex++;
        index1++;
    }

    while(index2 < secondHalfSize)
    {
        arr[mergedArrIndex] = &secondHalfArray[index2];
        mergedArrIndex++;
        index2++;
    }
}

void mergeSort(Person **arr, int firstElement, int lastElement)
{
    if (firstElement < lastElement)
    {
        int midElement = (firstElement + lastElement) / 2;
        mergeSort(arr, firstElement, midElement);
        mergeSort(arr, midElement + 1, lastElement);
        merge(&arr, firstElement, midElement, lastElement);

    }
}

And a pointer to a an array of structs that is Person *arrPersons The struct of person is as the following:

typedef struct Person
{
    char name[MAX_LENGTH_LINE];
    long id;
    float age;
} Person;

I'm calling the function in the main with:

mergeSort(&arrPersons, 0, 19);

(I have a list of 20 persons) where arrPersons is defined as Person *arrPersons And I'm trying to sort all of those persons by their id. I don't see why my merge sort is failing, I keep receiving a segmentation fault. Thank you for your help

Answer 1

Using this source code:

#include <stdio.h>
#include <stdlib.h>


#define MAX_LENGTH_LINE 50


typedef struct Person
{
    char name[MAX_LENGTH_LINE];
    long id;
    float age;
} Person;
 
 
void merge(Person **arr[], int firstElement, int midElement, int lastElement)
{
    int firstHalfSize  = midElement  - firstElement + 1;
    int secondHalfSize = lastElement - midElement;
    Person *firstHalfArray[firstHalfSize];
    Person *secondHalfArray[secondHalfSize];

    //char *p;
    //char *s;

    for (int i = 0; i < firstHalfSize; i++)
    {
        firstHalfArray[i] = *arr[firstElement + i];
    }

    for (int j = 0; j < secondHalfSize; j++)
    {
        secondHalfArray[j] = *arr[midElement + 1+ j];

    }

    int index1 = 0;
    int index2 = 0;
    int mergedArrIndex = firstElement;

    while (index1 < firstHalfSize && index2 < secondHalfSize)
    {

        if ((*firstHalfArray)[index1].id <= (*secondHalfArray)[index2].id)
        {
            arr[mergedArrIndex] = &firstHalfArray[index1];
            index1++;
        }
        else
        {
            arr[mergedArrIndex] = &secondHalfArray[index2];
            index2++;
        }
        mergedArrIndex++;
    }

    while (index1 < firstHalfSize)
    {
        arr[mergedArrIndex] = &firstHalfArray[index1];
        mergedArrIndex++;
        index1++;
    }

    while(index2 < secondHalfSize)
    {
        arr[mergedArrIndex] = &secondHalfArray[index2];
        mergedArrIndex++;
        index2++;
    }
}

void mergeSort(Person **arr, int firstElement, int lastElement)
{
    if (firstElement < lastElement)
    {
        int midElement = (firstElement + lastElement) / 2;
        mergeSort(arr, firstElement, midElement);
        mergeSort(arr, midElement + 1, lastElement);
        merge(&arr, firstElement, midElement, lastElement);

    }
}



int main( void )
{
    Person *arrPersons;
    arrPersons = malloc( sizeof( Person ) * 20 );
    
    mergeSort(&arrPersons, 0, 19);
}

The following is the output of running the program via gdb

gdb untitled2
....

(gdb) br main
Breakpoint 1 at 0xa3b: file untitled2.c, line 87.

(gdb) r
Starting program: untitled2 

Breakpoint 1, main () at untitled2.c:87
87  {

(gdb) c
Continuing.

Program received signal SIGSEGV, Segmentation fault.
0x0000555555554827 in merge (arr=0x7fffffffde88, firstElement=0, midElement=0, 
    lastElement=1) at untitled2.c:33

33          secondHalfArray[j] = *arr[midElement + 1+ j];
(gdb) bt

#0  0x0000555555554827 in merge (arr=0x7fffffffde88, firstElement=0, 
    midElement=0, lastElement=1) at untitled2.c:33
#1  0x0000555555554a30 in mergeSort (arr=0x7fffffffdf70, firstElement=0, 
    lastElement=1) at untitled2.c:79
#2  0x0000555555554a04 in mergeSort (arr=0x7fffffffdf70, firstElement=0, 
    lastElement=2) at untitled2.c:77
#3  0x0000555555554a04 in mergeSort (arr=0x7fffffffdf70, firstElement=0, 
    lastElement=4) at untitled2.c:77
#4  0x0000555555554a04 in mergeSort (arr=0x7fffffffdf70, firstElement=0, 
    lastElement=9) at untitled2.c:77
#5  0x0000555555554a04 in mergeSort (arr=0x7fffffffdf70, firstElement=0, 
    lastElement=19) at untitled2.c:77
#6  0x0000555555554a6e in main () at untitled2.c:91
(gdb) 

line 77 mergeSort(arr, firstElement, midElement);
Line 79 merge(&arr, firstElement, midElement, lastElement);
Line 33 secondHalfArray[j] = *arr[midElement + 1+ j];

Where
j = 0

The above should be all you need to know to fix the program.

Note: I did not give the fields of the array of Person any specific values.

suggest reading: merge sort

One thing to note is there is no usage of ** in the passing of parameters

Answer 2

What happened?

Applying & to an array will result to a pointer to array. So &arrPersons is pointer to array of Person.
Applying & to a pointer to array will result to a pointer to pointer to array. That is what really passed into merge. So arr in merge is a pointer pointed to a single element of pointer to array. So accessing arr with an offset other than zero will cause index out of range error.

Pass-by-value

Normally, parameters in C function is pass-by-value like:

void f(int x);
f(val);

The caller copy the value before passing it to f. So changing x in f does not effect val in the caller.

Pass-by-reference

Some functions need to change a variable in the caller. They should pass the argument by reference.

In C, the famous way for pass-by-reference is to pass pointer to the function like:

void f(int *p);
f(&val);

p is a pointer. So f can access val by *p.

Note:
Fundamentally, there is no pass-by-reference. Passing pointer can do the almost same thing as pass-by-reference. But exactly, it's passing the value of the pointer.

How to pass an array by reference to a function?

Array will decay into a pointer when passing it. c-fqa 6.3:

A reference to an object of type array-of-T which appears in an expression decays (with three exceptions) into a pointer to its first element; the type of the resultant pointer is pointer-to-T.

So direct passing a array to a function acept pointer is fine.

e.g. consider the sample code:

void f(int *p);
int a[4];
f(a);

a can be directly passing to f. And in the function f, p will be a pointer pointed to the first element of a.

In this case

Take pointer to an array is not necessary. Just passing the array to the function will work well.