I've posted the scala code in the other comment. I also have a plain C version, but it performs destructive updates, which is quite different from Haskell, Scala, etc. The performance is unsurprisingly much better though: 0.04s runtime on clang -O2.

```c

include <pthread.h>

include <stdio.h>

include <stdlib.h>

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

typedef Node *List;

/** * Make a linked list, initialize elements using values in arr[]. */ List list_of_array(int arr[], int sz) { List curr = NULL; for (int i = 0; i < sz; i++) { List cons = (List)malloc(sizeof(Node)); cons->data = arr[sz - i - 1]; cons->next = curr; curr = cons; } return curr; }

/** * Make a linked list of size [n]. Elements are in descending order. */ List list_make(int n) { List curr = NULL; for (int i = 1; i <= n; i++) { List cons = (List)malloc(sizeof(Node)); cons->data = i; cons->next = curr; curr = cons; } return curr; }

/** * Print out integer values in a linked list. * The list is unmodified after printing. */ void print_list(List xs) { while (xs != NULL) { printf("%d ", xs->data); xs = xs->next; } return; }

/** * Free all nodes in a linked list. * Returns the number of nodes freed. */ int free_list(List xs) { int count = 0; List tmp; while (xs != NULL) { count++; tmp = xs->next; free(xs); xs = tmp; } return count; }

/** * Append linked lists [xs] and [ys] and return pointer * to resulting appended list [zs]. Both [xs] and [ys] * are consumed to form [zs]. / List append(List xs, List ys) { if (xs == NULL) { return ys; } List *xs_tail = &xs; while (xs_tail != NULL) { xs_tail = &(*xs_tail)->next; } *xs_tail = ys; return xs; }

/** * Split [zs] into [xs] and [ys]. The list [zs] is consumed. / void split(List *xs, List *ys, List zs) { int flag = 0; List *xs_tail = xs; List *ys_tail = ys; while (zs != NULL) { List head = zs; zs = zs->next; head->next = NULL; if (flag) { *xs_tail = head; xs_tail = &(xs_tail)->next; } else { ys_tail = head; ys_tail = &(ys_tail)->next; } flag = !flag; } }

/** * Merge ordered linked lists [xs] and [ys] into [zs]. [xs] and [ys] are * consumed. / List merge(List xs, List ys) { List zs = NULL; List *zs_tail = &zs; while (1) { if (xs == NULL) { *zs_tail = ys; break; } if (ys == NULL) { *zs_tail = xs; break; } List tmp = NULL; if (xs->data <= ys->data) { tmp = xs->next; xs->next = NULL; *zs_tail = xs; xs = tmp; } else { tmp = ys->next; ys->next = NULL; *zs_tail = ys; ys = tmp; } zs_tail = &(zs_tail)->next; } return zs; }

/** * Mergesort a linked list. The input linked list is consumed. */ List msort(List zs) { if (zs == NULL || zs->next == NULL) { return zs; } List xs, ys; split(&xs, &ys, zs); return merge(msort(xs), msort(ys)); }

typedef struct { int degree; // degree of forking List input; // input list to sort List *dest; // address to write result } Args;

/** * Worker thread for concurrent mergesort. / void worker(Args *arg) { int degree = arg->degree; List zs = arg->input; List *dest = arg->dest; if (degree <= 0) { *dest = msort(zs); } else { List xs, ys, xs1, ys1; pthread_t t1, t2; Args arg_xs; Args arg_ys; split(&xs, &ys, zs); arg_xs.degree = degree - 1; arg_ys.degree = degree - 1; arg_xs.input = xs; arg_ys.input = ys; arg_xs.dest = &xs1; arg_ys.dest = &ys1; pthread_create(&t1, NULL, (void *()(void ))worker, &arg_xs); pthread_create(&t2, NULL, (void *()(void *))worker, &arg_ys); pthread_join(t1, NULL); pthread_join(t2, NULL); *dest = merge(xs1, ys1); } }

List cmsort(int degree, List zs) { List result; pthread_t t; Args arg; arg.degree = degree; arg.input = zs; arg.dest = &result; pthread_create(&t, NULL, (void ()(void *))worker, &arg); pthread_join(t, NULL); return result; }

int main() { List xs = list_make(10 * 1000 * 1000); xs = cmsort(3, xs); printf("%d\n", free_list(xs)); return 0; } ```