Nell'unione di tipo merge, perché non dividere immediatamente singoli elementi piuttosto che dividere ricorsivamente a metà?

Qualsiasi funzione ricorsiva può essere convertita in una iterativa. Normalmente, tuttavia, si usa semplicemente la ricorsione per un ordine di merge, perché la suddivisione a metà di volte si presta naturalmente alla ricorsione.

Per convertire una funzione ricorsiva in una iterativa di solito è necessaria un'implementazione di stack ausiliario per sostituire lo stack che la ricorsione fornisce gratuitamente. Tuttavia, Merge Sort può essere reso iterativo senza tale stack.

Unisci ordinamento, versione ricorsiva:

void mergeSort(int arr[], int l, int r)
{
   if (l < r)
   {
      int m = l+(r-l)/2; //Same as (l+r)/2 but avoids overflow for large l & h
      mergeSort(arr, l, m);
      mergeSort(arr, m+1, r);
      merge(arr, l, m, r);
   }
}

Unisci ordinamento, versione iterativa:

void mergeSort(int arr[], int n)
{
   int curr_size;  // For current size of subarrays to be merged
                   // curr_size varies from 1 to n/2
   int left_start; // For picking starting index of left subarray
                   // to be merged

   // Merge subarrays in bottom up manner.  First merge subarrays of
   // size 1 to create sorted subarrays of size 2, then merge subarrays
   // of size 2 to create sorted subarrays of size 4, and so on.
   for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
   {
       // Pick starting point of different subarrays of current size
       for (left_start=0; left_start<n-1; left_start += 2*curr_size)
       {
           // Find ending point of left subarray. mid+1 is starting 
           // point of right
           int mid = left_start + curr_size - 1;

           int right_end = min(left_start + 2*curr_size - 1, n-1);

           // Merge Subarrays arr[left_start...mid] & arr[mid+1...right_end]
           merge(arr, left_start, mid, right_end);
       }
   }
}

Si noti che la versione iterativa richiede un ciclo annidato. La funzione merge è esattamente la stessa in entrambi i casi.

Ulteriori letture
Ordinamento di merge iterativo

Perché l'intero punto è ridurre al minimo il numero di passaggi di unione.

Non sono proprio sicuro di cosa pensi che "iniziare con l'iterazione delle singole coppie di articoli nell'elenco in modo sequenziale". Immagino che tu intenda prendere la prima coppia, banalmente ordinarla, quindi unirla alla seconda coppia ordinata, quindi unire il risultato alla terza coppia. In tal caso dovrai eseguire n / 2 passaggi di unione, che in media richiedono iterare su n / 2 elementi ... quindi O (n ^ 2). Ma con l'ordinamento di unione "reale", hai solo log2 (n) unire passaggi, per una complessità totale di O (log (n) * n).

Perché devi attraversare la struttura ad albero. (e lo stack di chiamate lo attraversa per .)

Se costruisci l'albero dal basso verso l'alto, come stai essenzialmente suggerendo, non stai facendo meno lavoro; stai solo monitorando i risultati intermedi in modo diverso e rendendo l'algoritmo più complicato e meno intuitivo a mio parere.

Poiché la risposta di Robert Harvey implica (ma non lo afferma direttamente), la costruzione dal basso verso l'alto è un approccio più iterativo. Tuttavia, un approccio iterativo deve ancora creare tutti gli stessi container e tracker come lo stack di chiamata / albero per i valori di ritorno intermedi.

La differenza è che tu hai più lavoro da fare nella soluzione iterativa.

^{Cosa potrebbe valere la pena notare: se inizi a trattare con array che non si adattano alla memoria, potrebbe essere vantaggioso farlo come dici e costruire, molto più manualmente, dal basso verso l'alto - che potrebbe ti consente di lavorare in modo più intelligente da un disco.}