Il merge ha la stessa complessità asintotica del quick, quindi nn è certo in base alla velocità che il quick è preferibile.
Mergesort ha la sola pecca di non ordinare sul posto (richiede spazio extra) ed è preferibile ad esempio per ordinare liste.

Questo è mergesort (corretto)
codice:
void merge(int *array, int l, int m, int r){

	int i, j, k, aux[nr];

    for (i = m+1; i > l; i--) aux[i-1] = array[i-1];
    for (j = m; j < r; j++) aux[r+m-j] = array[j+1];
    for (k = l; k <= r; k++)
       if(aux[i] <= aux[j])
          array[k] = aux[i++];
	  else
		  array[k] = aux[j--];
}

void mergesort(int *array, int l, int r){

	int m = (r+l)/2;
    if(r <= l)
		return;

    mergesort(array, l, m);
    mergesort(array, m+1, r);
    merge(array, l, m, r);
}

questo è merge applicato alle liste

codice:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct linked{
	int value;
	struct linked *next;
	} *first = NULL, *new;


void add(int);
void show(void);
struct linked * merge(struct linked *, struct linked *);
struct linked *mergesort(struct linked *);


void main(){

	add(25);
	show();
	first = mergesort(first);
	show();
}


void add(int nr){

	srand(time(NULL));

	while(nr--){
		if(!(new = (struct linked *)malloc(sizeof(struct linked))))
			abort();
		(*(new)).value = rand()%100;
		(*(new)).next = NULL;
		(*(new)).next = first;
		first = new;
		}
}


struct linked * merge(struct linked *a, struct linked *b){

	struct linked head;
	struct linked *node = &head;

	while((a != NULL) && (b != NULL))
		if(a->value <= b->value){
			node->next = a;
			node = a;
			a = a->next;
			}
		else{
			node->next = b;
			node = b;
			b = b->next;
			}
		node->next = (a == NULL) ? b : a;

return head.next;
}


struct linked *mergesort(struct linked *node){

	struct linked *a = node;
	struct linked *b = node->next;

	if(node == NULL || node->next ==  NULL)
		return node;

	while((b != NULL) && (b->next != NULL)){
		node = node->next;
		b = b->next;
		}

	b = node->next;
	node->next = NULL;

return merge(mergesort(a), mergesort(b));
}

void show(){

	struct linked *temp;
	for(temp = first; temp->next != NULL; temp = temp->next)
		printf("%d ", temp->value);
	printf("\n");
}


Esistono inoltre algoritmi di sorting in grado di ordinare in tempo lineare (radix, counting) ma si applicano solo a casi specifici (quindi quick non è il piu veloce)





edit: ho incollato i codici perche cliccando sui link aggiunge degli spazi bianchi e nn trova le pagine