vielleicht wäre eine Parallelisierung interessant? Wenn man z.B. das Sortieren der Teillisten in jeweils einen Thread verlagert?
Parallelisierung ist bei Mergesort m.E. schwieriger als z.B. bei Quicksort, weil die Threads "synchronisiert" werden müssen, und zwar in der Weise, daß erst, wenn die beiden Teilsortierungen fertig sind - dann aber ohne Verzug - beide Teilmengen verschmolzen werden müssen, während hingegen bei Quicksort die Sortierungen der Teilmengen unabhängig voneinander weiterwerkeln können. Aber mit den richtigen Konzepten (Metaphoren? Keine Ahnung) ist eine solche Synchronisierung sicher möglich.
Am Mergesort selbst läßt sich zum einen die Rekursion beseitigen, aber der Algorithmus als solcher bleibt dabei bestehen, nur der Stackbedarf wird vermieden.
Die eigentliche Optmierung des Mergesorts besteht allerdings darin, von einem Tiefen- zu einem Breitenalgorithmus überzugehen, konkret zum sog. Natura Mergesort, das bei entsprechender Implementation in der Lage ist, Vorsortierungen auszunutzen und ggf. auch invertierte Teilfolgen "richtigherum zu invertieren".