I'm trying to sort strings using merge sort

Question

Problem Statement

In this problem we have given a text document employee.txt in which employee names and their ages are stored, such as this data:

abc 45
xyz 23
pqr 23
xuv 25
tcs 76

And we have to sort this on string i.e. on names using merge sort and store them into new text document called sorted_name_employee.txt.

I have tried something but this is not giving an appropriate output.

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

struct employee
{
    char name[10];
    int age;
} emp[20];

void m_sort(struct employee *a, int low, int up);
void merge(struct employee *a, struct employee *temp, int low1, int up1, int low2, int up2);
int total_records(struct employee *a);
void copy(struct employee *a, struct employee *temp, int low, int up);
void write_into_file(struct employee *a, int n);

int main()
{
    int i = 0, n;
    struct employee emp[20];
    n = total_records(emp);
    //printf("n in main:- %d\n", n);
    m_sort(emp, 0, n - 1);
    /*for (i = 0; i <= n; i++)
    {
        printf("%s %d\n", emp[i].name, emp[i].age);
    }*/
    write_into_file(emp, n);
    printf("Data has been written into 'sorted_name_emp.txt'");
}

int total_records(struct employee *a)
{
    int i = 0;
    FILE *fp;
    fp = fopen("employee.txt", "r");
    if (fp == NULL)
    {
        printf("Error!");
        exit(1);
    }
    else
    {
        while (!feof(fp))
        {
            fscanf(fp, "%s %d", a[i].name, &a[i].age);
            i++;
        }
    }
    return (i - 1);
}

void m_sort(struct employee *a, int low, int up)
{
    int mid;
    struct employee temp_emp[20];
    if (low < up)
    {
        mid = (low + up) / 2;
        m_sort(a, low, mid);
        m_sort(a, mid + 1, up);
        merge(a, temp_emp, low, mid, mid + 1, up);
        copy(a, temp_emp, low, up);
    }
}

void merge(struct employee *a, struct employee *temp, int low1, int up1, int low2, int up2)
{
    int i = low1, j = low2, k = low1;
    while ((i <= up1) && (j <= up2))
    {
        if (strcmp(a[i].name, a[j].name) <= 0)
        {
            strcpy(temp[k].name, a[i].name);
            temp[k].age = a[i].age;
            k++;
            i++;
        }
        else
        {
            strcpy(temp[k].name, a[j].name);
            temp[k].age = a[j].age;
            k++;
            j++;
        }
    }
    while (i <= up1)
    {
        strcpy(temp[k].name, a[i].name);
        temp[k].age = a[i].age;
        k++;
        i++;
    }
    while (j <= up2)
    {
        strcpy(temp[k].name, a[j].name);
        temp[k].age = a[j].age;
        k++;
        j++;
    }
}

void copy(struct employee *a, struct employee *temp, int low, int up)
{
    int i = 0;
    for (i = 0; i <= up; i++)
    {
        strcpy(a[i].name, temp[i].name);
        a[i].age = temp[i].age;
    }
}

void write_into_file(struct employee *a, int n)
{
    int i;
    FILE *fp;
    fp = fopen("sorted_name_emp.txt", "w");
    if (fp == NULL)
    {
        printf("Error!");
        exit(1);
    }
    for (i = 0; i <= n; i++)
    {
        fprintf(fp, "%s %d\n", a[i].name, a[i].age);
    }
}

Actual Ouptput in sorted_name_emp.txt:

abc 45
pqr 23
xuv 25
xyz 56
tcs 76

Answer 1

There are multiple problems:

• if n is the number of records, for (i = 0; i <= n; i++) iterates one time too many. You should use i < n instead of i <= n.

• while (!feof(fp)) is always wrong to read and parse a file. Use this instead:

    while (fscanf(fp, "%s %d", a[i].name, &a[i].age) == 2) {
        i++;
    }
  

• total_records returns i - 1, which is cumbersome and error prone. You should just return i and fix the code elsewhere to handle n as the number of records.

• m_sort(emp, 0, n - 1); seems incorrect, but your implementation of m_sort() does assume that the last argument is the index to the last element. So it would be correct if n was the number of elements but since you return i - 1 in total_records, you actually pass the index to the element before the last one, so this is the reason the last element is not sorted correctly.

• mid = (low + up) / 2; does not pose a problem for just a few records, but if sorting a large array, low + up could exceed the range of type int and cause undefined behavior. You should write mid = low + (up - low) / 2;

• the loop in function copy iterates from i=0, whereas it should start at i = low.

• you forget to close the file in total_records and write_into_file with fclose(fp)

• struct employee emp[20]; defined in main actually shadows the global array emp[20] defined at the global scope with the same name.

• there is no need to copy each structure member separately, you can just copy the structures directly with temp[k] = a[i];...

Passing the index to the last element is error prone. It is more idiomatic in C and less error prone to pass the index to the element past the end of the slice to sort. This avoids cumbersome and confusing +1 / -1 adjustments.

Here is a modified version:

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

struct employee {
    char name[10];
    int age;
};

void m_sort(struct employee *a, int low, int up);
void merge(struct employee *a, struct employee *temp, int low1, int up1, int low2, int up2);
int total_records(struct employee *a, int max_index, const char *filename);
void copy(struct employee *a, struct employee *temp, int low, int up);
void write_into_file(struct employee *a, int n, const char *filename);

int main(void) {
    struct employee emp[20];
    int n = total_records(emp, 20, "employee.txt");
    m_sort(emp, 0, n);
    write_into_file(emp, n, "sorted_name_emp.txt");
    printf("Data has been written into 'sorted_name_emp.txt': %d lines\n", n);
    return 0;
}

int total_records(struct employee *a, int max_index, const char *filename) {
    int i = 0;
    FILE *fp = fopen(filename, "r");
    if (fp == NULL) {
        printf("Cannot open %s: %s\n", filename, strerror(errno));
        exit(1);
    }

    while (i < max_index && fscanf(fp, "%9s %d", a[i].name, &a[i].age) == 2) {
        i++;
    }
    fclose(fp);
    return i;
}

void m_sort(struct employee *a, int low, int up) {
    if (up - low > 1) {
        struct employee temp_emp[20];
        int mid = low + (up - low) / 2;
        m_sort(a, low, mid);
        m_sort(a, mid, up);
        merge(a, temp_emp, low, mid, mid, up);
        copy(a, temp_emp, low, up);
    }
}

void merge(struct employee *a, struct employee *temp, int low1, int up1, int low2, int up2)
{
    int i = low1, j = low2, k = low1;
    while (i < up1 && j < up2) {
        if (strcmp(a[i].name, a[j].name) <= 0) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    while (i < up1) {
        temp[k++] = a[i++];
    }
    while (j < up2) {
        temp[k++] = a[j++];
    }
}

void copy(struct employee *a, struct employee *temp, int low, int up) {
    for (int i = low; i < up; i++) {
        a[i] = temp[i];
    }
}

void write_into_file(struct employee *a, int n, const char *filename) {
    FILE *fp = fopen(filename, "w");
    if (fp == NULL) {
        printf("Cannot open %s: %s\n", filename, strerror(errno));
        exit(1);
    }
    for (int i = 0; i < n; i++) {
        fprintf(fp, "%s %d\n", a[i].name, a[i].age);
    }
    fclose(fp);
}

Output file contents:

abc 45
pqr 23
tcs 76
xuv 25
xyz 23