Sto sviluppando un algoritmo di ordinamento sul posto che lascia la matrice in uno stato in cui è fondamentalmente una successione di sottosequenze ordinate di qualsiasi dimensione (la maggior parte sono più grandi di log2(size(array)) ); quindi unisce le suddette sottosezioni in atto. Una volta raggiunto lo stato descritto, l'algoritmo nella sua forma corrente unisce semplicemente le prime due sottosequenze, quindi unisce il risultato con la seguente sottosequenza, ecc ... Si noti che al momento della fusione, sappiamo dove iniziano le sottosequenze ordinate, non dobbiamo trovarli di nuovo.
Anche se funziona bene, suppongo che questo schema di fusione sia subottimale e credo che dovrebbe essere possibile utilizzare uno schema di fusione più intelligente. Il miglior algoritmo che potrei pensare sarebbe un algoritmo che cerca le più piccole successioni successive e le unisce, quindi si ripete fino a quando tutto è stato fuso. L'idea è che unire prima sequenze più piccole è più economico, quindi dovremmo unire le più grandi solo alla fine.
Esiste un algoritmo più efficiente per unire n sequenze successive sul posto?
Come richiesto, immaginiamo di voler ordinare il seguente array:
10 11 12 13 14 9 8 7 6 5 0 1 2 3 4
Il mio algoritmo farà cose che sono totalmente irrilevanti per la domanda, ma lascia l'array nel seguente stato:
10 11 12 13 14 0 5 6 7 8 9 1 2 3 4
^ ^ ^
I caret mostrano dove iniziano abbastanza grandi sottosequenze ordinate nell'array; nel codice attuale, corrispondono a iteratori o indici a seconda dell'astrazione che si utilizza. Il prossimo passo è quello di unire queste sottosequenze per ordinare l'array (si noti che tutti sono più grandi di log2(size(array)) se questo è importante, ma potrebbero avere dimensioni diverse). Per unire le diverse parti di questo array, la mossa più intelligente sembra fondere l'ultima sottosequenza con quella centrale, lasciando la matrice nello stato seguente:
10 11 12 13 14 0 1 2 3 4 5 6 7 8 9
^ ^
... quindi due uniscono le due sottosequenze rimanenti in posizione in modo che l'array sia effettivamente ordinato. Come ho già detto, ci possono essere fino a log2(size(array)) di tali sottosezioni prima del passaggio di unione sul posto.
La mia attuale soluzione per la fase di fusione richiede un po 'di indiretta: gli iteratori puntati dai carnet sono memorizzati in un elenco, quindi creo un heap minimo in cui ogni elemento è uno degli iteratori di lista e la funzione di confronto associa a ogni iteratore il distanza tra i suoi vicini. Quando due sottosequenze vengono unite, inserisco un valore dall'heap e rimuovo gli iteratori corrispondenti dall'elenco. Ecco fondamentalmente cosa fa il mio algoritmo C ++:
template<typename Iterator, typename Compare=std::less<>>
auto sort(Iterator first, Iterator last, Compare compare={})
-> void
{
// Code irrelevant to the question here
// ...
//
// Multi-way merge starts here
std::list<Iterator> separators = { first, /* beginning of ordered subsequences */, last };
std::vector<typename std::list<Iterator>::iterator> heap;
for (auto it = std::next(separators.begin()) ; it != std::prev(separators.end()) ; ++it)
{
heap.push_back(it);
}
auto cmp = [&](auto a, auto b) { return std::distance(*std::prev(a), *std::next(a)) < std::distance(*std::prev(b), *std::next(b)); };
std::make_heap(heap.begin(), heap.end(), cmp);
while (not heap.empty())
{
std::pop_heap(heap.begin(), heap.end(), cmp);
typename std::list<Iterator>::iterator it = heap.back();
std::inplace_merge(*std::prev(it), *it, *std::next(it), compare);
separators.erase(it);
heap.pop_back();
}
}
Ho scritto l'algoritmo in C ++ perché trovo più semplice ragionare sugli iteratori, ma una risposta algoritmica generale è benvenuta.