[Teorico/c++] Natural merge sort

[Neptune]

Salve a tutti,
l'altro giorno a lezione abbiamo visto in linea teorica (ma in futuro sarà da applicare in c++) il Natural merge sort, ovvero un modo per ordinare delle liste mediante divisione delle stesse in catene e successiva fusione.
Nel preambolo c'è stato detto che il normale merge sort fa un forte uso degli indici e quindi in una struttura come la lista, in cui non si ha un accesso diretto, porterebbe ad un grosso spreco di risorse. C'è stato quindi introdotto questo natural merge sort.

E' stato però spiegato in tutta fretta a fine lezioni e sinceramente mi è sfuggito totalmente il suo funzionamento.
Nelle slide prima dice che:

Spezzetta la lista in sottoliste (dette catene), e per farlo inizia a leggere sequenzialmente finchè gli elementi che incontra sono ordinati li mantiene in una catena, quando ne trova uno non ordinato spezza e inizia un'altra catena. Poi fa vedere graficamente come successivamente fa il merge delle catene a due a due e nel farlo riordina gli elementi, fino ad avere una lista ordinata.

Fin qui, almeno in via teorica tutto chiaro, anche se non si capisce in linea pratica come effettuare il tutto.

Arrivando nel passo successivo delle slide, dove credo appunto affronta lo sviluppo pratico (più che altro in pseudocodice) parla della lista originale L e di due sottoliste A e B, ma sinceramente mi sono abbondantemente perso perchè ci sta solo pseudocodice senza commenti ed i commenti che ha fatto a lezione non sono riuscito a capirli perchè andava di fretta.

Se qualcuno saprebbe spiegarmi come si traforma la parte teorica in teoria e cosa centrano quelle due "sottoliste" mi farebbe un grande favore. Intanto cerco su google anche se sto trovando solo cose in inglese che mi stanno un pò confondendo (Il nome italiano quale sarebbe? Ordinamento per fuzione Naturale? o come?).

Vi ringrazio,
Neptune.

[Neptune]

Ho riguardato minuziosamente le dispense, è queste sono le conclusioni a cui sono giunto:

La prima fase dell'algoritmo è la suddivisione della lista in catene (*). Qui si iniziano a leggere in maniera sequenziale gli elementi della lista andando a creare nuove catene, ogni catena finisce quando si incontra un elemento che è più grande del successivo o è più piccolo del precedente; Quindi sostanzialmente avremo o catene di singoli elementi, o delle catene di elementi ordinati di grandezza variabile.

Nel secondo passo dell'algoritmo le catene vengono distribuite in maniera alternata su due liste ausiliare (A e B). In questo secondo passo dagli esempi dele slide si nota come:
Non si tiene conto dell'ordine delle catene su due liste ausiliare ma se due catene adiacenti risultano avere elementi disposti in maniera ordinata allora vengono direttamnete fuse tra loro;

Infine si passa al terzo passo in cui si fondono le catene. Ma in questo passo come si procede? si cerca di predisporre le catene nella maniera più ordinata, ma se ho la catena X = <5,44,65> e la catena Y = <3,4,83> quale catena verrà messa per prima?

Il terzo passo riguardante la fusione non mi è ben chiaro come avviene, se due catene adiacenti vengono fuse e riordinate tra loro prima di essere inserite nella lista principale, ed in questo caso che algoritmo viene utilizzato per riordinarle, o se vengono semplicemente disposte in maniera il più ordinate possibile nella lista principale, ma nel caso delle due catene di sopra quale viene messa per prima? quella che ha il primo elemento più piccolo o quella che ha l'ultimo elemento più piccolo?

(*) Una catena non è altro che una sottolista;

Riguardo al terzo passo potrei andare a logica ma non vorrei che quello che produco non è "l'algoritmo del natural merge sort" ma l'algoritmo di Neptune E dato che mi serve per gli esami preferirei essere sicuro di questo terzo passo. Tra l'altro su internet si parla ovunque di merge sort e non di questo naturl merge sort (anche in siti in cui si parlava di natural merge sort alla fine si finiva per parlare di merge sort e basta, non so).