Quelle méthode de tri convient le mieux au traitement parallèle?

Je pense que fusionne la sorte

Vous pouvez diviser le jeu de données et faire des opérations parallèles sur elles.

Comme le genre de fusion, Quicksort peut également être facilement parallélédisé en raison de sa nature de la division et de la conquête. Les opérations de partition individuelles sur place sont difficiles à paralléliser, mais une fois divisées, différentes sections de la liste peuvent être triées en parallèle.

Un avantage de QuickSort parallèle sur d'autres algorithmes de tri parallèle est qu'aucune synchronisation n'est requise. Un nouveau fil est démarré dès qu'un subliste est disponible pour qu'il fonctionne et ne communique pas avec d'autres threads. Lorsque toutes les threades terminées, le tri est effectué.

http://en.wikipedia.org/wiki/quicksort

Cela dépend complètement de la méthode de parallélisation. Pour l'informatique générale multithread, une sorte de fusion fournit des propriétés assez fiables en équilibrage de la charge et à la localisation de la mémoire. Pour un grand réseau de tri dans le matériel, une forme de trotteuse, biologique ou de coque est réellement meilleure Si vous voulez de bonnes performances O (Log² n).

Je pense que la fusion serait la meilleure réponse ici. Étant donné que l'idée de base de la fusion est de diviser le problème en solutions individuelles.solvez-les et de les fusionner.

C'est ce que nous faisons aussi en traitement parallèle aussi. Divisez le problème en tout dans les petites instructions de l'unité pour calculer parallien, puis rejoindre les résultats. Merci

Il est en train de fusion car le tri est effectué sur deux sous-tableaux et ils sont comparés et triés à la fin. Ceux-ci peuvent être effectués en parallèle

Quelques remarques aléatoires:

1. De nombreuses discussions sur la facilité de paralléliser QuicksTort ignorer la sélection de pivotements. Si vous parcourez la matrice pour le trouver, vous avez introduit un composant séquentiel de temps linéaire.
2. Quicksort n'est pas facile à mettre en œuvre dans la mémoire distribuée. Il y a une discussion dans le livre Kumar
3. Ouais, je sais, on ne devrait pas utiliser de tri de bulle. Mais «Trier de transposition étrange», qui est plus ou moins équivalente, est en fait un très bon exercice de programmation parallèle. En particulier pour le parallélisme de la mémoire distribuée. C'est l'exemple le plus facile d'un réseau de tri, qui est très faisable dans MPI et tel.