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

"I don't see why my merge sort is failing, I keep receiving a segmentation fault." -- You may want to read these two links: 1. How to debug small programs 2. What is a debugger and how can it help me diagnose problems? — Andreas Wenzel
– Andreas Wenzel, Commented Aug 2, 2020 at 14:09
Have you used a debugger to determine where exactly in your program the segmentation fault is occuring? And have you inspected the values of all variables at that location to determine whether they have expected values? — Andreas Wenzel
– Andreas Wenzel, Commented Aug 2, 2020 at 14:19
Although I don't want to encourage you to ask other people to debug your programs for you, it would be easier for other people to help you if you provided a minimal reproducible example in which you call the function merge with data that reliably produces a segmentation fault. — Andreas Wenzel
– Andreas Wenzel, Commented Aug 2, 2020 at 14:21
If you are able to reproduce the segmentation fault with a small amount of data (for example 5 persons instead of 20 persons), then your program will also be easier to debug. You will be able to run your program line by line in a debugger, while monitoring the values of all variables, to see if they have the expected values. — Andreas Wenzel
– Andreas Wenzel, Commented Aug 2, 2020 at 14:32
regarding: ` Person *arrPersons` This does NOT define an array of 20 Person elements. Did you use something like arrPersons = malloc( sizeof( Person ) * 20 ); ? — user3629249
– user3629249, Commented Aug 2, 2020 at 15:11

user3629249 · Accepted Answer · 2020-08-02 16:02:22Z

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

yao99 · Accepted Answer · 2020-08-02 20:47:01Z

1

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.

edited Aug 2, 2020 at 20:47

answered Aug 2, 2020 at 17:27

yao99

9085 silver badges13 bronze badges

10 Comments

David C. Rankin Over a year ago

"pointer of array" -> "pointer to array" (nit) "Pass by Reference" - In C there is no pass by reference. You are passing an address by value simulating a pass by reference. That is an important distinction. (I know what you mean, but the OP may take you literally) Better to link to the C standard for a question tagged C. C and C++ are different languages.

yao99 Over a year ago

@DavidC.Rankin I am just confused, after googling, I find that some pages like cplusplus and geeksforgeeks use both "pointer of" and "pointer to". But using "pointer to" more. Does they have different meaning? Or just "pointer to" is more common, so i can replace all "pointer of" to "pointer to".

David C. Rankin Over a year ago

"pointer of" what? A pointer is a normal variable that holds the address to another object as its value. (i.e. the pointer "points to" where the other object can be found in memory) Simple case int a = 5, b = &a; There b holds the address of a as its value (we say b points to a). I know what you mean, and I suspect this may also be a language to and of translation issue, but generally we say a pointer "points to" a memory address rather than being a "pointer of" that address. Be wary of what you read in general from the internet unless it is from the actual standard.

yao99 Over a year ago

@DavidC.Rankin Thanks for explanation. And sorry for the wrong link, C has the same thing, but this answer should like to C version. I will edit it.

David C. Rankin Over a year ago

Glad to help. This is a fantastic site for the discussion of programming information -- that's how we all learn :)

|

Collectives™ on Stack Overflow

Merge sort with pointer to pointer array not working

2 Answers 2

Comments

What happened?

Pass-by-value

Pass-by-reference

How to pass an array by reference to a function?

In this case

10 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

What happened?

Pass-by-value

Pass-by-reference

How to pass an array by reference to a function?

In this case

10 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related