reverse.c

#include <stdio.h>
#include <string.h>
#include <stdint.h>
#include <time.h>
#include <assert.h>

inline void swap_char(char *a, char *b) {
    *a ^= *b; *b ^= *a; *a ^= *b;
}

// super slow recursion O(n^2)
char *rev_a(char *s) {
    char head = *s;
    if (head == '\0'){
        return s;
    }
    rev_a(s+1);
    // copy substring
    char *current = s;
    while(1) {
        if (*(current+1) == '\0') {
            *current = head;
            break;
        } else {
            *current = *(current+1);
        }
        ++current;
    }
    return s;
}

// maximum stack depth is the length of s.
// O(n)
char *rev_s(char *s) {
    int len = strlen(s);
    if (len > 1) {
        char head = *s;
        char *tail_ptr = s+len-1;
        *s = *(tail_ptr);
        *(tail_ptr) = '\0';
        rev_s(s+1);
        *(tail_ptr) = head;
    }
    return s;
}

// binary swap, inspired by merge sort
char *rev_b(char *s) {
    int len = strlen(s);
    if (len > 1) {
        // int mid = len / 2 + (len & 1); // ignore privot
        int mid = (len + 1) / 2; // ignore privot
        rev_b(s+mid);
        // TODO: swap s, s+mid, strlen(s+mid)
        for (int i = 0; i < mid; i++) {
            char tmp = s[i];
            s[i] = s[i+mid];
            s[i+mid] = tmp;
        }
        rev_b(s+mid);
    }
    return s;
}

// depth O(n) 
int _helper_c(char *s, char *current) {
    if (*current == '\0') {
        return 0;
    } else {
        int co_idx = _helper_c(s, current+1);
        if (co_idx < current-s) {
            /*
            char tmp = s[co_idx];
            s[co_idx] = *current;
            *current = tmp;
            */
            swap_char(s+co_idx, current);
        }
        return co_idx + 1;
    }
} 

char *rev_c(char *s) {
    _helper_c(s, s);
    return s;
}

// depth O(n) 

/*
int _helper_d(void *s, void *current) {
    if (*((char*)current) == '\0') {
        return 0;
    } else {
        uint64_t *str = s, *cur = current;
        // const int step = sizeof(uint64_t) / sizeof(char);
        int co_idx = _helper_c(s, (void *)(cur+1));
        if (co_idx < current-s) {
            uint64_t tmp = str[co_idx];
            str[co_idx] = *cur;
            *cur = tmp;
            // remember the inter reverse of each uint64_t 
            _swap_char_(s  , s+7);
            _swap_char_(s+1, s+6);
            _swap_char_(s+2, s+5);
            _swap_char_(s+3, s+4);
            _swap_char_(current  , current+7);
            _swap_char_(current+1, current+6);
            _swap_char_(current+2, current+5);
            _swap_char_(current+3, current+4);
        }
        return co_idx + 1;
    }
} 

char *rev_d(char *s) {
    _helper_d((void*)s, (void*)s);
    return s;
}
*/
char *rev_for(char *str) {
    int len = strlen(str);
    for (int i = 0; i < len/2; i++) {
        char c = str[i];
        str[i] = str[len - i - 1];
        str[len - i - 1] = c;
    }
    return str;
}

int main(int argc, char const* argv[])
{
    char str[1050000], backup[1050000], reversed[1050000];
    FILE *FD = fopen(argv[1], "r");
    if (FD != NULL) {
        fscanf(FD, "%s", str);
        fclose(FD);
    } else {
        strcmp(str, "hello world");
    }

    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        reversed[i] = str[len - i - 1];
    }
    reversed[len] = '\0';
    strcpy(backup, str);

    char *(*reverse_fuctions[])(char *) = {rev_for, rev_a, rev_b, rev_s, rev_c};
    int n_reverse_function = sizeof(reverse_functions) / sizeof(reverse_functions[0]);
    puts("absc");
    for (int i = 0; i < n_reverse_functions; i++) {
        clock_t begin = clock();

        reverse_fuctions[i](str);
        assert(strcmp(str, reversed) == 0);
        reverse_fuctions[i](str);
        assert(strcmp(str, backup) == 0);

        clock_t end = clock();
        double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
        printf("Case %d# %lfs\n", i+1, time_spent);
    }
    /*
    printf("%s\n", rev(str));
    printf("%s\n", rev(str));
    printf("%s", rev(rev(str)));
    */
    return 0;
}

Needs compile options -O, or remove inline from the declaration of swap_char manually.

$ ./a.out case1k
absc
Case 1# 0.000010s
Case 2# 0.000959s
Case 3# 0.000186s
Case 4# 0.000892s
Case 5# 0.000014s
$ ./a.out case4k
absc
Case 1# 0.000033s
Case 2# 0.013263s
Case 3# 0.000650s
Case 4# 0.006442s
Case 5# 0.000047s
$ ./a.out case8k
absc
Case 1# 0.000058s
Case 2# 0.033567s
Case 3# 0.001025s
Case 4# 0.029117s
Case 5# 0.000089s
$ ./a.out case1M
absc
Case 1# 0.004937s
[1] 10302 segmentation fault ./a.out case1M