Quindi ho il codice che produce k intervalli ordinati in un array di dimensioni n. Quello che sto facendo di brainstorming è la possibilità di sul posto di fusione di questi intervalli in un singolo intervallo / array ordinato. Il problema è la gestione della complessità dello spazio.
Per semplicità, considera il problema di sul posto unendo solo due intervalli in un singolo intervallo ordinato (la lunghezza dell'array).
Per cominciare, sto cercando un algoritmo che integri le operazioni sul posto, il che significa che non ho bisogno di un array ausiliario di dimensione n come nel caso di mergesort , in quanto ciò sarebbe poco pratico con la dimensione dei miei dati. Inoltre, devo evitare algoritmi ricorsivi.
C'è ovviamente la questione dell'efficienza associata a questo, in termini di numero di confronti, scambi e località di riferimento, ma questo è qualcosa di cui sono a conoscenza.
Nota: ho studiato questo argomento alcuni (e per un po 'di tempo), quindi fai attenzione a postare link ad altre domande o soluzioni banali (ho considerato l'inserimento di ordinamento), a meno che tu non abbia una buona ragione per farlo.