Какой из следующих алгоритмов сортировки вставками, по вашему мнению, работает быстрее?

Два дефекта делают тест бессмысленным:

1. В макросе TEST вы используете tmp - end + begin для вычисления указателя end массива tmp, но это должно быть tmp + (end - begin).

2. insertion_sort_2() возвращает отсортированный массив, но он не содержит все элементы входного массива, поэтому это нечто иное, чем алгоритм сортировки. Например, вот прогон с N=10:

   before: 5298, 8764, 9261, 4325, 1305, 2502, 7606, 3141, 8770, 331
   after:  8764, 8764, 8764, 8764, 8764, 8764, 8770, 9261, 9261, 9261 
   

   Условие внутреннего цикла — i > begin && *(i - 1) > tmp, что означает, что в данном случае цикл завершается i == begin || *(i - 1) <= tmp. Оператор после цикла *(i-1) = tmp может и будет записываться перед массивом, что является неопределенным поведением. Должно быть *i = tmp;.

Как только вы исправите эти две проблемы, тест будет работать примерно за одно и то же время при компиляции с gcc -O2:

$ for((i=0; i < 3; i++)); do ./a.out ; done
Test insertion_sort_1 :         OK      831 ms
Test insertion_sort_2 :         OK      815 ms
Test insertion_sort_1 :         OK      947 ms
Test insertion_sort_2 :         OK      955 ms
Test insertion_sort_1 :         OK      831 ms
Test insertion_sort_2 :         OK      867 ms

За исключением меток, ассемблер этих двух функций один и тот же.

Я заменил ваш макрос TEST на функцию benchmark() для простоты отладки, добавив отсутствующий заголовок и несколько проверок ошибок:

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

#define N 100000

bool check(const int* begin, const int* end);

void benchmark(const char *name, void (*f)(int *, int *), int* begin,  int* end) {
    printf("Test %s : ", name);
    size_t n = end - begin;
    int *tmp = malloc(sizeof(int) * n);
    if (!tmp) {
        perror("");
        exit(1);
    }
    memcpy(tmp, begin, sizeof(int) * n);
    long long b = clock();
    (*f)(tmp, tmp + n);
    long long e = clock();
    if (check(tmp, tmp + n))
        printf("\tOK");
    else\
        printf("\tWrong");
    printf("\t%lld ms\n", (e - b) * 1000 / CLOCKS_PER_SEC);\
    free(tmp);
}

bool check(const int* begin, const int* end) {
    for(const int* cur = begin; cur < end - 1; ++cur) {
        if (*cur > *(cur + 1))
            return false;
    }
    return true;
}

int *geneArr(unsigned n) {
    int* arr = malloc(sizeof(int) * n);
    if (!arr) {
        perror("");
        exit(1);
    }
    for(int i = 0; i < n; ++i)
        arr[i] = rand() % 10000;
    return arr;
}

void swap(int* a, int* b) {
    if (a == b) return;
    int c = *a;
    *a = *b;
    *b = c;
}

void insertion_sort_1(int *begin, int *end) {
    for (int *cur = begin + 1; cur < end; cur++) {
        int tmp = *cur;
        int *pos = cur;
        for (int *i = cur; i > begin && *(i - 1) > tmp; --i) {
            *i = *(i - 1);
            pos = i - 1;
        }
        *pos = tmp;
    }
}

void insertion_sort_2(int *begin, int *end) {
    for (int *cur = begin + 1; cur < end; cur++) {
        int tmp = *cur;
        int *i = cur;
        for (; i > begin && *(i - 1) > tmp; --i)
            *i = *(i - 1);
        *i = tmp;
    }
}

int main() {
    srand(time(0));
    int* arr = geneArr(N);
    benchmark("insertion_sort_1", insertion_sort_1, arr, arr + N);
    benchmark("insertion_sort_2", insertion_sort_2, arr, arr + N);
    free(arr);
}