sort

A set of ordered elements are reordered by size (as long as a comparison relationship that can return true or false is defined, not a certain value comparison).

Merge sort

Merging and sorting is a divide and conquer strategy, in which two sorted arrays are arranged according to the size relationship at a time. The algorithm uses recursion to sort and merge the elements in the array length (1,2...n/4,n/2,n).

Algorithm implementation

void merge(long long int* arr, long long int* tmp, int left, int right, int rightEnd) {
    int i, leftEnd, num, tmpPos;
    leftEnd = right - 1;
    tmpPos = left;
    num = rightEnd - left + 1;

    while(left <= leftEnd && right <= rightEnd) {
        if (arr[left] <= arr[right]) {
            tmp[tmpPos++] = arr[left++]; 
        } else {
            tmp[tmpPos++] = arr[right++];
        }
    }

    while(left <= leftEnd) {
        tmp[tmpPos++] = arr[left++];
    }

    while(right <= rightEnd) {
        tmp[tmpPos++] = arr[right++];
    }

    for (i = 0; i < num; i++, rightEnd--) {
        arr[rightEnd] = tmp[rightEnd];
    }
}

void mSort(long long int* arr, long long int* tmp, int left, int right, int len) {
    int center;
    int i;

    if (left < right) {
        center = (left + right) / 2;
        mSort(arr, tmp, left, center, len);
        mSort(arr, tmp, center + 1, right, len);
        merge(arr, tmp, left, center + 1, right);
        printf("Merge parameters:%d %d Result:", left, right);
        for (i = 0; i < len; i++) {
            printf("%lld ", arr[i]);
        }
        printf("\n");
    }
}

long long int* elrSortMerge(long long int* arr, int len) {
    long long int* tmp;
    
    tmp = malloc(len * sizeof(long long int));
    if (tmp) {
        mSort(arr, tmp, 0, len - 1, len);
        free(tmp);
    } else {
        printf("no space for sort merge\n");
    }
    
    return arr;
}

Debugging call

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

int main(int argc, char **argv){
    int i;
    long long int arr[] = {6, 2, 4, 1, 3, 5, 0, 8, 9, -1, 7};
    elrSortMerge(arr, 11);
    printf("%d\n", (int)(sizeof(arr) / sizeof(long long int)));
    for (i = 0; i < 11; i++) {
        printf("%lld   ", arr[i]);
    }
    printf("\n");
    return 0;
}

output

Merge parameter: 0 1 Result: 2 6 4 1 3 5 0 8 9 - 1 7 
Merge parameter: 0 2 Result: 2 4 6 1 3 5 0 8 9 - 1 7 
Combined parameters: 3 4 Results: 2 4 6 1 3 5 0 8 9 - 1 7 
Combined parameters: 3 5 Results: 2 46 1 35 8 9 - 1 7 
Merge parameter: 0 5 result: 1 23 4 5 6 0 8 9 - 1 7 
Combined parameters: 6 7 Results: 1 23 4 5 6 0 8 9 - 1 7 
Combined parameters: 6 8 results: 1 23 4 5 6 0 8 9 - 1 7 
Combined parameters: 9 10 results: 1 23 4 5 6 0 8 9 - 1 7 
Combined parameters: 6 10 results: 1 23 4 5 6 - 1 07 8 9 
Combined parameters: 0 10 results: - 1 0 1 2 3 4 5 6 7 8 9