Devo implementare l'algoritmo di merge sort in c++. Ho scritto la funzione mergeSort ma non ho capito come funziona la merge. Potreste aiutarmi a capire come funziona la merge?
Codice:
void mergeSort(int v[], int sinistra, int destra)
{
if (sinistra < destra)
{
int centro = (sinistra + destra) / 2;
mergeSort(v, sinistra, centro);
mergeSort(v, centro + 1, destra);
merge(v, sinistra, centro, destra);
}
void merge(int v[], int sinistra, int centro, int destra)
{
int dim = destra - sinistra + 1;
int *u = new int[dim];
int i;
int i_s = sinistra;
int i_d = centro + 1;
for (i = 0; i < dim; ++i)
{
if (i_s <= centro)
{
if (i_d <= destra)
{
if (v[i_s] < v[i_d])
{
u[i] = v[i_s++];
}
else
{
u[i] = v[i_d++];
}
}
else
{
u[i] = v[i_s++];
}
}
else
{
u[i] = v[i_d++];
}
}
for (i = 0; i < dim; ++i)
{
v[sinistra + i] = u[i];
}
delete[] u;
}
}
Ultima modifica: