Sto rivedendo gli algoritmi di base di un libro intitolato Algorithms di Robert Sedgewick, e mi sono imbattuto in un problema in MergeSort che sono, purtroppo, in difficoltà a risolvere. Il problema è sotto:
Sublinear Extra Space. Develop a merge implementation that reduces that extra space requirement to max(M, N/M), based on the following idea: Divide the array into N/M blocks of size M (for simplicity in this description, assume that N is a multiple of M). Then, (i) considering the blocks as items with their first key as the sort key, sort them using selection sort; and (ii) run through the array merging the first block with the second, then the second block with the third, and so forth.
Il problema che ho con il problema è che, in base all'idea che Sedgewick consiglia, il seguente set di matrici non verrà ordinato: {0, 10, 12}, {3, 9, 11}, {5, 8, 13}. L'algoritmo che uso è il seguente:
- Dividi l'intero array in sottoschemi di dimensioni M.
- Esegui selezione ordinamento su ciascuno dei sottoarray.
- Unisci ognuno dei sottoarray usando il metodo raccomandato da Sedgwick in (ii). (È qui che incontro il problema di dove memorizzare i risultati dopo l'unione.)
Questo porta a voler aumentare le dimensioni dello spazio ausiliario necessario per gestire almeno due sottoreti alla volta (per la fusione), ma in base alle specifiche del problema, ciò non è consentito.
Ho anche preso in considerazione l'utilizzo dell'array originale come spazio per un subarray e l'utilizzo dello spazio ausiliario per il secondo subarray. Tuttavia, non posso immaginare una soluzione che non finisca per sovrascrivere le voci del primo sottoarray.
Qualche idea su altri modi in cui ciò può essere fatto?
NOTA: se questo è supposto essere su StackOverflow.com, per favore fammi sapere come posso spostarlo. Ho postato qui perché la domanda era accademica.