Personalmente non conosco il ragionamento alla base di questi libri e non pretendo di avere una visione unica su questo problema.
Tuttavia, l'ordinamento merge esterno può essere implementato esattamente in due fasi, e nessuno dei due stage contiene una suddivisione ricorsiva. In altre parole, in entrambi gli stadi, c'è solo un livello di suddivisione.
Scegli il numero di suddivisione N.
Fase 1: partizionare arbitrariamente i dati di input in N suddivisioni. Ordina all'interno di ciascuna suddivisione.
Fase 2: creare N code FIFO, ciascuna alimentata dalla suddivisione corrispondente nell'ordine ordinato. Eseguire un mergesort N-way (heap binario o ordinamento selezione) sbirciando la testa di ogni coda e rimuovendo l'elemento più piccolo, inviandolo alla coda FIFO di output. Ogni volta che una coda FIFO diventa vuota, si alimenterà dai dati rimanenti dalla suddivisione corrispondente. Le dimensioni delle code FIFO vengono scelte in base alla memoria disponibile, ma l'algoritmo funziona correttamente anche se tutte le code FIFO hanno dimensione 1.
Come spiegato sopra, non esiste una suddivisione ricorsiva del problema.
Questa è solo un'osservazione. Non so se gli autori di libri considerino la suddivisione ricorsiva come una parte fondamentale di D & C.
Esistono molti schemi di ordinamento unione esterni. Quello sopra descritto è solo un esempio. Questi altri schemi potrebbero fare uso della suddivisione ricorsiva. Non ne so molto di quelli quindi non potrò commentare.