TLista Lista_mergeListas(TLista *L1, TLista * L2) {
    TLista LMerged;
    Lista_crear(&LMerged);

    TNodo *ptr_rec1, *ptr_rec2;
    ptr_rec1 = L1->inicio;
    ptr_rec2 = L2->inicio;

    while (ptr_rec1 != NULL && ptr_rec2 != NULL) {
        if (ptr_rec1->elem < ptr_rec2->elem) {
            Lista_insertar(&LMerged, ptr_rec1->elem);
            ptr_rec1 = ptr_rec1->sig;
        } else {
            Lista_insertar(&LMerged, ptr_rec2->elem);
            ptr_rec2 = ptr_rec2->sig;
        }
    }

    while (ptr_rec1 != NULL) {
        Lista_insertar(&LMerged, ptr_rec1->elem);
        ptr_rec1 = ptr_rec1->sig;
    }

    while (ptr_rec2 != NULL) {
        Lista_insertar(&LMerged, ptr_rec2->elem);
        ptr_rec2 = ptr_rec2->sig;
    }

    return LMerged;
}

void partirLista(TLista* L, TLista* primeraMitad, TLista * segundaMitad) {
    //caso base: L tiene 2 elementos
    int lonLista = Lista_tamanho(L);
    if (lonLista == 2) {
        Lista_insertar(primeraMitad, L->inicio->elem);
        Lista_insertar(segundaMitad, L->fin->elem);
    } else {
        TNodo* curNode = L->inicio;
        int i;
        for (i = 0; i < lonLista / 2; i++) {
            Lista_insertar(primeraMitad, curNode->elem);
            curNode = curNode->sig;
        }
        for (i = lonLista / 2; i < lonLista; i++) {
            Lista_insertar(segundaMitad, curNode->elem);
            curNode = curNode->sig;
        }
    }
}

void Lista_mergesort(TLista * L) {
    if (L->numElem > 1) {
        TLista primeraMitad, segundaMitad;
        Lista_crear(&primeraMitad);
        Lista_crear(&segundaMitad);
        partirLista(L, &primeraMitad, &segundaMitad);
        Lista_mergesort(&primeraMitad);
        Lista_mergesort(&segundaMitad);
        *L = Lista_mergeListas(&primeraMitad, &segundaMitad);
    }
}