Salve a tutti ragazzi, apro questo topic per chiedervi un aiuto riguardo al seguente algoritmo che ho implementato in c++.
E' da un po di tempo che tento di implementare il Merge sort ma sempre con scarsi risultati.
Penso che l'errore sia nella funzione merge, ma non riesco a proprio a capire cosa ci sia di sbagliato.. spero riusciate ad aiutarmi!
Ecco il codice che sono riuscito a scrivere finora..
Grazie

codice:
#include<iostream>
#include<cstdlib>
#include<ctime>

using namespace std;

void stampa( int* A, int dim_vett )
{
	for ( int i = 0; i < dim_vett; i++ )
		cout << A[i] << " ";
}

int sentinella( int* A, int dim_vett )
{
	int max = A[0];
	for ( int i = 1; i < dim_vett; i++ )
		if ( A[i] > max )
			max = A[i];
	return max+1;
}

void merge( int* A, int left, int &center, int right )
{
	int n1 = center - left;
	int n2 = right - center;
	
	int* L = new int[n1+1];
	int* R = new int[n2+1];
	
	int i, j;

	for ( i = 0; i < n1; i++ )
		L[i] = A[left +i];

	for ( j = 0; j < n2; j++ )
		R[j] = A[center +j];
	
	L[n1+1] = sentinella(A, right);
	R[n2+1] = sentinella(A, right);
	
	i = 0;
	j = 0;
	
	for ( int k = left; k < right; k++ )
	{
		if ( L[i] <= R[j] )
		{
			A[k] = L[i];
			i++;
		}
		else
		{
			A[k] = R[j];
			j++;
		}
	}
}

void merge_sort( int* A, int left, int right )
{
	if ( left == right )
		return;
	int center = ( left + right ) / 2;

	merge_sort(A, left, center);
	merge_sort(A, center+1, right);
	merge(A, left, center, right);
}

int main()
{
	int dim_vett;
	cout << "\nDimensione: ";
	cin >> dim_vett;
	
	int* A = new int[dim_vett];
	srand(time(NULL));

	for ( int i = 0; i < dim_vett; i++ )
		A[i] = rand() % 100;
	
	cout << "Vett = ";
	stampa(A, dim_vett);
	
	cout << "\nVett_Sorted = ";
	merge_sort(A, 0, dim_vett);
	stampa(A, dim_vett);

	return 0;
}