[linux-l] [OT]: algorithmische Frage: Sort parallelisieren

[Oliver Bandel]

On Wed, Jan 03, 2007 at 05:32:33PM +0100, Volker Grabsch wrote:
[...] 
> Auch wenn Quicksort bekannter ist und häufiger eingesetzt wird, hat
> das doch eher was mit den Datenstrukturen zu tun (Arrays in C/Fortran/...).
> Verwendet man hingegen verkettete Listen, in funktionalen Sprachen
> etwas ganz Natürliches, dann ist auf jeden Fall Mergesort das Mittel
> der Wahl.

Interessanter Aspekt... das mit den funktionalen Sprachen :)

Aber Listen sind doch eher ineffektiv.
Nimmt man da nicht besser Baumstrukturen?


> 
> Da beim Parallelisieren ohnehin die Daten vom einen Rechner zum anderen
> müssen, ist eine Sortierung am Platz aber eh nicht mehr sinnvoll. Daher
> lautete meine Empfehlung Mergesort, weil die wenigen Vorteile von
> Quicksort überhaupt nicht zum Tragen kommen.
[...]

Naja, wenn das Netz die Bremse darstellt, dann weissich eben nicht,
ob das eine gute Idee ist, die Daten über's Netz zu schicken.
Aber wenn eine Maschine mehrereProzessoren hat und die Aufteilung
gut funktioniert, kann man doch einiges an Speedup erwarten

Also ich werde mir dann gleich mal das Mergesort anschauen.
Ist jadoch eine recht interessante Sache mit dem parallelisierten
Sort.

Gruß,
   Oliver