Divide & Conquer

#include <iostream>
#include <sys/time.h>
#include <dos.h>
#include <sys\timeb.h>
using namespace std;
 
typedef char ItemLista;
#define ITEMLISTAINDEFINIDO 0
class NodoLista{
	ItemLista dato;
	NodoLista *sig;
public:
	NodoLista(ItemLista dato,NodoLista *sig=NULL){
		this->dato=dato;
		this->sig=sig;
	}
	void mostrar(){cout<<dato;}
	void mostrarseguro(){
		cout<<dato<<" ";
		if(sig!=NULL){sig->mostrarseguro();}
	}
	void setsig(NodoLista *sig){this->sig=sig;}
	NodoLista *getsig(){return sig;}
	void setdato(ItemLista dato){this->dato=dato;}
	ItemLista getdato(){return dato;}
};
 
class Lista{
	NodoLista *cab;
	int tam;
	NodoLista *obtenernodo(int pos){
		if(esvacia() || pos>tam) return NULL;
		NodoLista *nodo=cab; pos--;
		while(pos>0){
			nodo=nodo->getsig();
			pos--;
		}
		return nodo;
	}
	unsigned int suma(NodoLista *nodo){
		if(nodo==NULL) return 0;
		else return (nodo->getdato() + suma(nodo->getsig()));
	}
public:
	Lista(){
		cab=NULL;
		tam=0;
	}
	bool esvacia(){return (tam==0);}
	int size(){ return tam;}
	ItemLista obtener(int pos){
		if(esvacia() || pos>tam) return ITEMLISTAINDEFINIDO;
		NodoLista *nodo=cab; pos--;
		while(pos>0){
			nodo=nodo->getsig();
			pos--;
		}
		return nodo->getdato();
	}
	void insertar(ItemLista dato,int pos=1){
		insertar(new NodoLista(dato),pos);
	}
	void insertar(NodoLista *nodo,int pos=1){
		if(esvacia()){
			cab=nodo;
		}else{
			if(pos>tam) pos=tam+1;
			if(pos<=1){
				nodo->setsig(cab);
				cab=nodo;
			}else{
				NodoLista *n=obtenernodo(pos-1);
				nodo->setsig(n->getsig());
				n->setsig(nodo);
			}
		}
		tam++;
	}
	void borrar(int pos=1){
		if(esvacia()) return;
		if(pos>tam) pos=tam;
		NodoLista *nodo;
		if(pos<=1){
			nodo=cab;
			cab=cab->getsig();
			free(nodo);
		}else{
			nodo=obtenernodo(pos-1);
			NodoLista *temp=nodo->getsig();
			nodo->setsig(temp->getsig());
			free(temp);
		}
		tam--;
 
	}
	void mostrarseguro(){
		cab->mostrarseguro();
	}
	unsigned int suma(){ return suma(cab);}
};
 
void combinar(Lista *L,int com, int med1, int med2, int fin){
	ItemLista datocom,datomed2;
//	cout<<"["<<com<<","<<med1<<"]-["<<med2<<","<<fin<<"]"<<endl;
	int i=com;
	while(i<fin){
		datocom=L->obtener(com);
		datomed2=L->obtener(med2);
//		cout<<"\t"<<"dato1="<<datocom<<" dato2="<<datomed2;
		if(datocom>=datomed2){
			L->borrar(med2);
			L->insertar(datomed2,i);
//			cout<<"\t"<<datocom<<">"<<datomed2<<" ==> ";
			med2++;com++;
		}else{
			L->borrar(com);
			L->insertar(datocom,i);
//			cout<<"\t"<<datocom<<"<"<<datomed2<<" ==> ";
			com++;
		}
		i++;
//		L->mostrarseguro();cout<<endl;
		if(med2>fin) break;
	}
}
void mergesort(Lista *L,int com,int fin){
	if(fin<=com) return;
	int medio=(com+fin)/2;
	mergesort(L,com,medio);
	mergesort(L,medio+1,fin);
	combinar(L,com,medio,medio+1,fin);
}
 
int main(int argc, char *argv[]){
	Lista *L = new Lista();
	struct timeb t_start, t_end;
	int t_diff;
 
	srand(time(NULL));
	cout<<"Creando Lista"<<endl;
	for(int i=2000;i>0;i--){
		L->insertar(rand()%26+65);
	}
	cout<<endl<<"Lista: ";L->mostrarseguro();
	cout<<endl<<"Tamanio: "<<L->size();
	cout<<endl<<"Suma de datos(control): "<<L->suma();
 
	cout<<endl<<endl;
	ftime(&t_start);
	mergesort(L,1,L->size());
	ftime(&t_end);
	cout<<"Lista Ordenada: ";L->mostrarseguro();
	cout<<endl<<"Tamanio: "<<L->size();
	cout<<endl<<"Suma de datos(control): "<<L->suma();
 
	cout<<endl<<endl;
	t_diff = (int) (1000.0 * (t_end.time - t_start.time)+ (t_end.millitm - t_start.millitm));
	cout<<"Tiempo en ordenar: "<<t_diff<<"ms";
 
    cout<<endl;system("PAUSE");
    return 0;
}