Sorting algorithm – Merge Sort

This algorithm is fast but consumes much memory as you can think of no use to sort arrays of more than 40000 items.
Here is my implementation in C + +, using recursion.

#include <time.h>
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
const int MAX = 30000;
int data[MAX+1];
void mergeSort(int desde, int hasta) {
    if (hasta-desde <= 1) return;
    int middle = (desde+hasta)/2;
    mergeSort(desde, middle);
    mergeSort(middle, hasta);
    int dPtr, lPtr, rPtr, result[hasta];
    dPtr = lPtr = desde;
    rPtr = middle;
    while (dPtr < hasta) {
        if (lPtr == middle)
            result[dPtr++] = data[rPtr++];
        else if(rPtr == hasta)
            result[dPtr++] = data[lPtr++];
        else if (data[lPtr] < data[rPtr])
            result[dPtr++] = data[lPtr++];
        else
            result[dPtr++] = data[rPtr++];
    }
    while(desde < hasta)
        data[desde++] = result[desde];
}

int main() {
    int n;
    printf("Ingresar cuandos datos se ordenarann");
    scanf("%d", &n);
    for(int i=0; i<n ;i++)
        data[i] = rand()%1000000000;
    mergeSort(0, n); //aqui ordena el array de enteros
    for(int i=0; i<n ;i++)
    cout<<data[i]<<" ";
}

As you can see the algorithm is simple, separate all components of the array, then the mixture neatly as the name implies, this separation makes the algorithm does not need to compare all the elements.

         {18, 6, 9, 1, 4, 15, 12, 5, 6, 7, 11}
       {18, 6, 9, 1, 4}     {15, 12, 5, 6, 7, 11}
     {18, 6}   {9, 1, 4}   {15, 12, 5}  {6, 7, 11}
    {18} {6}  {9} {1, 4}   {15} {12, 5} {6} {7, 11}
    {18} {6}  {9} {1}{4}   {15} {12} {5} {6} {7} {11} //end of split section.
    {18} {6}  {9} {1, 4}   {15} {5, 12} {6} {7, 11}
     {6, 18}  {1, 4, 9}     {5, 12, 15} {6, 7, 11}
       {1, 4, 6, 9, 18}     {5, 6, 7, 11, 12, 15}
         {1, 4, 5, 6, 6, 7, 9, 11, 12, 15, 18}

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s