Esiste un algoritmo di ordinamento che non sia intrinsecamente sequenziale e che sia distribuibile per attività?

Hai trascurato sleep-sort che è distribuito come attività. Ecco un'implementazione per la shell Bourne:

input="10 4 5 1"
for n in $input; do
  (sleep $n; echo $n) &
done

Al termine del programma, l'elenco ordinato dei numeri viene stampato sullo standard output. (Si noti che potrebbe essere necessario aggiungere la gestione dei lavori per determinare quando terminano i sottoprocessi.)

Gli algoritmi basati su tentativi ed errori dovrebbero adattarsi alla tua descrizione, in quanto le prove possono essere eseguite in parallelo.

Gli esempi potrebbero essere:

• Bogosort , che rimischia i dati finché non vengono ordinati

• StackSort , che cerca algoritmi di ordinamento su stackoverflow, eseguendoli uno a uno fino a quando viene restituita una risposta corretta

Lascia scherzi:
Mergesort è sicuramente un buon candidato per implementare un algoritmo parallelo.

Un algoritmo generale per l'ordinamento parallelo potrebbe essere simile a questo:

1. Dividi i dati in k junks (dove k è il numero di agenti di elaborazione).
2. Ordina ogni posta indesiderata in parallelo.
3. Unisci i giunchi ordinati.

Come @amon fa notare nel suo commento, il terzo passo può anche essere eseguito parzialmente in parallelo con il passo 2, se l'algoritmo di ordinamento selezionato restituisce prima gli elementi piccoli.

Vedi la discussione di Knuth sull'ordinamento delle fusioni polifase con selezione di sostituzione nel volume 2 di ACP. O google "ordinamento esterno". Questi tipi risalgono agli albori dell'informatica quando i computer spesso non avevano abbastanza memoria per ordinare tutti i dati, ma avevano più unità nastro collegate. Se si sostituiscono le unità nastro con flussi di dati tra processi, gli algoritmi funzionano ancora in modo eccezionale. Ho implementato questo algoritmo nei primi anni '80 per un sistema che non aveva un programma di ordinamento fornito dal sistema operativo.