Merge sort: sono le copie di array supplementari necessarie?

StackOverflow https://stackoverflow.com/questions/4304768

Domanda

In "Introduzione agli algoritmi" l'algoritmo merge sort è implementato con una funzione di supporto chiamata MERGE(A, p, q, r) - che è la fusione di due sequenze precedentemente ordinati.

Questa funzione introduce due array supplementari L e R. 

MERGE(A, p, q, r)
1 n1 ← q − p + 1
2 n2 ←r − q
3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
.....

Per "create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]" Capisco allocare memoria aggiuntiva per entrambi.

E 'possibile ri-scrittura di questa funzione, in modo che io non avrò bisogno della memoria aggiuntiva, e di operare direttamente in A?

È stato utile?

Soluzione

Certo. Si chiama sul posto merge sort.

Wikipedia dire che è complicato - ma non è sempre vero. Alcuni non sono così complicato come altri , se non si preoccupano il runtime .

Ci sono un paio di varianza, alcuni sono stabili, alcuni sono non stabili. Vedere la sezione "implementazione" sotto NIST DIAGS per qualche esempio.

Altri suggerimenti

Sì, si chiama sul posto merge sort, ma come Wikipedia dice:

  

Ordinamento sul posto è possibile (per esempio, utilizzando le liste piuttosto che array), ma è molto complicato, e offrirà piccoli miglioramenti delle prestazioni nella pratica, anche se le piste algoritmo in O (n log n). (Katajainen, Pasanen & Teuhola 1996)

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top