Merge sort

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

/* Trộn hai đoạn ĐÃ SẮP a[lo..giua) và a[giua..hi) vào tmp,
   rồi chép ngược lại vào a. */
static void tron(int *a, int *tmp, size_t lo, size_t giua, size_t hi)
{
    size_t i = lo, j = giua, k = lo;

    while (i < giua && j < hi)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   /* dấu bằng giữ ổn định */

    while (i < giua) tmp[k++] = a[i++];
    while (j < hi)   tmp[k++] = a[j++];

    memcpy(&a[lo], &tmp[lo], (hi - lo) * sizeof *a);
}

/* Sắp nửa khoảng a[lo..hi). */
static void ms(int *a, int *tmp, size_t lo, size_t hi)
{
    if (hi - lo < 2) return;                  /* 0 hoặc 1 phần tử, đã sắp */

    size_t giua = lo + (hi - lo) / 2;

    ms(a, tmp, lo, giua);
    ms(a, tmp, giua, hi);
    tron(a, tmp, lo, giua, hi);
}

/* Trả về 0 nếu ổn, -1 nếu hết bộ nhớ. */
int merge_sort(int *a, size_t n)
{
    if (n < 2) return 0;

    int *tmp = malloc(n * sizeof *tmp);

    if (tmp == NULL) return -1;

    ms(a, tmp, 0, n);

    free(tmp);

    return 0;
}

/* Trộn [3, 27, 38, 43] với [9, 10, 82]

   i -> 3 27 38 43        j -> 9 10 82        tmp:
   3 <= 9   -> lay 3      tmp: 3
   27 > 9   -> lay 9      tmp: 3 9
   27 > 10  -> lay 10     tmp: 3 9 10
   27 <= 82 -> lay 27     tmp: 3 9 10 27
   38 <= 82 -> lay 38     tmp: 3 9 10 27 38
   43 <= 82 -> lay 43     tmp: 3 9 10 27 38 43
   het nua trai           tmp: 3 9 10 27 38 43 82

   Moi phan tu duoc chep dung MOT lan. */

#include <stdio.h>

typedef struct { int khoa; char nhan; } Muc;

/* Mảng vào:  3a 1a 3b 1b
   Chia đôi:  [3a 1a]  [3b 1b]
   Sắp từng nửa: [1a 3a]  [1b 3b]

   Trộn với <= :  1a <= 1b -> lay 1a
                  3a >  1b -> lay 1b
                  3a <= 3b -> lay 3a
                  con 3b
                  Ket qua: 1a 1b 3a 3b     ON DINH

   Trộn với <  :  1a <  1b sai (bang) -> lay 1b
                  1a <  3b -> lay 1a
                  3a <  3b sai (bang) -> lay 3b
                  con 3a
                  Ket qua: 1b 1a 3b 3a     DAO THU TU        */

#include <stddef.h>

typedef struct Node { int data; struct Node *next; } Node;

/* Tách danh sách làm đôi bằng hai con trỏ nhanh chậm, xem Bài 21.6.
   Trả về nửa sau, và cắt nửa trước bằng cách đặt next của nút cuối là NULL. */
static Node *tach_doi(Node *head)
{
    if (head == NULL || head->next == NULL) return NULL;

    Node *cham = head;
    Node *nhanh = head->next;

    while (nhanh != NULL && nhanh->next != NULL) {
        cham  = cham->next;
        nhanh = nhanh->next->next;
    }

    Node *sau = cham->next;

    cham->next = NULL;      /* cắt */

    return sau;
}

/* Trộn hai danh sách đã sắp. Chỉ nối lại con trỏ, KHÔNG cấp phát gì. */
static Node *tron_list(Node *a, Node *b)
{
    Node  gia;              /* nút giả để bỏ trường hợp riêng cho nút đầu */
    Node *duoi = &gia;

    gia.next = NULL;

    while (a != NULL && b != NULL) {
        if (a->data <= b->data) { duoi->next = a; a = a->next; }
        else                    { duoi->next = b; b = b->next; }

        duoi = duoi->next;
    }

    duoi->next = (a != NULL) ? a : b;      /* nối nốt phần còn lại */

    return gia.next;
}

/* Sắp danh sách. Trả về đầu mới. */
Node *merge_sort_list(Node *head)
{
    if (head == NULL || head->next == NULL) return head;

    Node *sau = tach_doi(head);

    head = merge_sort_list(head);
    sau  = merge_sort_list(sau);

    return tron_list(head, sau);
}

/* Giai đoạn 1: tạo các đoạn đã sắp.
   Đọc M phần tử vừa RAM, sắp trong bộ nhớ, ghi ra một tệp tạm. */
int tao_doan(const char *tep_vao, size_t M, size_t *so_doan)
{
    FILE *f = fopen(tep_vao, "rb");

    if (f == NULL) return -1;

    int *bo_dem = malloc(M * sizeof *bo_dem);

    if (bo_dem == NULL) { fclose(f); return -1; }

    size_t k = 0;
    size_t doc;

    while ((doc = fread(bo_dem, sizeof *bo_dem, M, f)) > 0) {
        qsort(bo_dem, doc, sizeof *bo_dem, so_sanh_int);

        char ten[64];

        snprintf(ten, sizeof ten, "doan-%zu.tmp", k);

        FILE *g = fopen(ten, "wb");

        if (g == NULL) { free(bo_dem); fclose(f); return -1; }

        fwrite(bo_dem, sizeof *bo_dem, doc, g);
        fclose(g);
        ++k;
    }

    free(bo_dem);
    fclose(f);
    *so_doan = k;

    return 0;
}

/* Giai đoạn 2: trộn k đoạn cùng lúc bằng một heap nhỏ nhất kích thước k.
   Xem Bài 23.4. Mỗi lần lấy phần tử nhỏ nhất trong k đầu đoạn,
   ghi ra, rồi đọc phần tử kế tiếp của đoạn đó vào heap. */