Contenido del curso

Bienvenido al Curso

1
Algoritmos y Estructuras de Datos: Curso Básico
02:17 min

Introducción a los algoritmos

Algoritmos de ordenamiento

Recursividad

Divide and conquer y programación dinámica

Algoritmos 'Greedy'

Grafos y árboles

¿Cómo comparar Algoritmos?

41
Comparación de Algoritmos: Complejidad y Ritmo de Crecimiento
11:14 min

¿Qué sigue?

42
Resolución de Problemas Básicos con Algoritmos y Estructuras de Datos
02:26 min

Tomar examen

El algoritmo MergeSort es un algoritmo del tipo Divide and Conquer, en este dividimos el array de entrada en dos mitades, se invoca la función merge_sort(arr,low,mid); y merge_sort(arr,mid+1,high);

En cada una de esas mitades y luego une las dos mitades ordenadas, la función merge() se encargará de unir las dos mitades.

El comando merge(arr, low, mid, high) es un proceso clave que une las partes ordenadas, a continuación te comparto la implementación estándar utilizada por codeblocks:

//Divide : Divide the n-element array into two n/2-element subarrays.
//Conquer : Sort the two subarrays recursively using merge sort
//Combine : Merge the two sorted subsequences to form the sorted array

#include<stdio.h>
int arr[20];       // array to be sorted

int main()
{
  int n,i;
  
  printf("Enter the size of array\n");  // input the elements
  scanf("%d",&n);
  printf("Enter the elements:");
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
  
  merge_sort(arr,0,n-1);  // sort the array
  
  printf("Sorted array:");  // print sorted array
  for(i=0;i<n;i++)
    printf("%d",arr[i]);
  
  return 0;
}

int merge_sort(int arr[],int low,int high)
{
  int mid;
  if(low<high)
  {
    mid=(low+high)/2;
   // Divide and Conquer
    merge_sort(arr,low,mid);
    merge_sort(arr,mid+1,high);
   // Combine
    merge(arr,low,mid,high);
  }
  
  return 0;
}

int merge(int arr[],int l,int m,int h)
{
  int arr1[10],arr2[10];  // Two temporary arrays to
                             hold the two arrays to be merged
  int n1,n2,i,j,k;
  n1=m-l+1;
  n2=h-m;

  for(i=0;i<n1;i++)
    arr1[i]=arr[l+i];
  for(j=0;j<n2;j++)
    arr2[j]=arr[m+j+1];

  arr1[i]=9999;  // To mark the end of each temporary array
  arr2[j]=9999;

  i=0;j=0;
  for(k=l;k<=h;k++)  //process of combining two sorted arrays
  {
    if(arr1[i]<=arr2[j])
      arr[k]=arr1[i++];
    else
      arr[k]=arr2[j++];
  }
  
  return 0;
}

Ordenamiento de Arrays con MergeSort en C

Comentarios

Francisco Joel Morando Pinedo

student•

Aquí está la explicación de Merge Sort que Platzi no quiso (o no supo) explicarnos. Y es gratis!!!

https://youtu.be/TGRt7SQ1Xoc

JUAN FRANCISCO ochoa lomas

student•

Wow que buena explicación, de hecho me recordó a la universidad, y bueno creo que aqui es valido decir por que no es tan mala la escuela y el tiempo que se dedica a desarrollar un tema, muchas gracias. faltaron las diapositivas jajaja

Gloriq Lopez

student•

Es un poco molesto, para otros temas dan explicación hasta gráfica y todo, pero algoritmos como estos que no son tan fácil que digamos lo dan como un articulo, generalizando que todo aquel que lea ya lo comprenderá. Tendrían que hacer una clase (video) explicando cada linea de código de este Algoritmo.

Alfredo Godinez

student•

comparto tu comentario, creo que ese debe ser el plus que nos deberían de compartir los profes en este tipo de cursos, aclaro que no es malo el material que dan, si deberían de ahondar mas a fondo, porque muchos temas los ven por encima y deberían ser mas concisos.

alexander garcia castañeda

student•

que parte no entienden?

Moisés Manuel Morín Hevia

student•

Gonzalo Gramaglia

student•

Wow. Super útil este gráfico para entender el algoritmo. Muchas gracias!!

Daniel Santiago Perez Ducuara

student•

Es realmente un algoritmo de QuickSort, no de MergeSort

Eduardo Kiriakos Piazza

student•

Aqui la inplementación del mergeSort en python con algunos print statements para entender mucho mejor lo que hace el código!

import random

def mergeSort(arr):
  if len(arr) > 1:
    mid = len(arr) // 2
    left = arr[:mid]
    rigth = arr[mid:]
    print(f"Dividing left: {left} rigth {rigth}")

    mergeSort(left)
    mergeSort(rigth)
    # Esta es una de las dudas que me surgió al intentar entender recursividad.
    print("¿Cuándo se ejecuta esta línea?")

    i = 0
    j = 0
    k = 0

    while i < len(left) and j < len(rigth):
      if left[i] < rigth[j]:
        arr[k] = left[i]
        i += 1
      else:
        arr[k] = rigth[j]
        j += 1
      
      k += 1

    while i < len(left):
      arr[k] = left[i]
      i += 1
      k += 1 

    while j < len(rigth):
      arr[k] = rigth[j]
      j += 1
      k += 1 

    print(f'comparando izquierda {left}, derecha {rigth}')
    print(arr)
    print('-' *50)

  return arr


if __name__ == '__main__':
  n = int(input('What is the length of the array? '))

  arr = [random.randint(0, 100) for i in range(n)]
  print(arr)
  print('-' * 20)
  ordered_arr = mergeSort(arr)
  print(ordered_arr)

Harrinson Quintero

student•

Genial tu codigo en Python que va mostrando el proceso 👍🏻👍🏻

Diego Portillo

student•

Muy bueno el aporte, en cuando a la pregunta comentada en el código, la línea se ejecuta cuando los elementos llegaron a la longitud de 1 y no pueden seguir dividiendose

Henry Caicedo Velasco

student•

Esta es la diferencia entre Merge Sort Vs Quick Sort. (https://youtu.be/es2T6KY45cA) (Tiene subtitulos en español, activenlos)

Elisa Zamarron Muñoz

student•

Es muy interesante el video, también los otros que tiene ese canal sobre algoritmos de ordenamiento. Me ayudaron a entender mejor, muchas gracias :)

Ignacio Saccomano

student•

Muy bueno

Henry Leonardo Rodríguez Pérez

student•

La verdad a este código me parece que le hace falta muchísimo para lo que esperaría de un curso de Platzi.

Para empezar, no se explica bien (siendo un algoritmo complicado por usar la recursividad), declara primero la función que divide y luego la que combina (¿Cómo va a hacer eso?, la función de dividir llama a la de combinar, ¿no?), además, tiene un límite en cuanto a los número del array, y termina el array con “9999”, ¿es en serio? ¿En donde se usa ese fin del array?

Les dejo mi código por si puedo ayudar a alguien que se perdió por este código tan incompleto:

https://github.com/santiago-perez-03/sorting-algorithms/tree/main/mergeSort

Cuando ejecutes el código, si mandas el parametro -VERBOSE te va mostrando paso a paso lo que va haciendo durante el proceso de ordenamiento.

Brayan García

student•

Por si se ve muy confuso les dejo este vídeo con el que pude entender mucho mejor el algoritmo, les recomiendo que lo vean lo implementa de una forma más sencilla https://youtu.be/8nINr-bnbnw?list=PLwissfvpGGmgmG7D1v7NSYAsXPnXZLQsX

Jorge Torres Arboleda

student•

Gran aporte

Reinaldo Mendoza

student•

Me quedo mas claro con el video, gracias

Victor Muchica Farfan

student•

En esta lectura siento que nos hubieran soltado en el coliseo romano junto a los leones, a ver como se defiende uno y logra salir vivo. Al menos en el curso de C listas enlazadas, el profesor "explico" el codigo.

Este video me ayudo a entender el algoritmo https://www.youtube.com/watch?v=TzeBrDU-JaY

Puse los printf para entender mejor el codigo con los comentarios Lo mejor es probar con numeros pequeños(ordenar 3 numeros) y luego van agregando mas valores. hasta que logren entender el codigo.

#include<stdio.h>
int main()
{
  int n,i,arr[20]; //declaracion array de 20 elementos
  printf("Enter the size of array: ");
  scanf("%d",&n); //valor del tamaño del array
  printf("Enter the elements:\n");
  for(i=0;i<n;i++){
    scanf("%d",&arr[i]);//ingresa los valores al arreglo
  }
  printf("merge_sort(arr,0,%d)\n",n-1);
  merge_sort(arr,0,n-1);  //aca ocurre la magia

  printf("Array Ordenado:");  //imprime arreglo ordenado
  for(i=0;i<n;i++)
    printf("%d,",arr[i]);

  return 0;
}

int merge_sort(int arr[],int low,int high)
{
  int mid;
  if(low<high)
  {
    mid=(low+high)/2;
   // Divide en 2 al array
    printf("ordena toda izquierda -> merge_sort(arr,%d,%d)\n",low,mid);
    merge_sort(arr,low,mid); //izquierda
    printf("ordena toda derecha -> merge_sort(arr,%d,%d)\n",mid+1,high);
    merge_sort(arr,mid+1,high); //derecha
   // Combina
    printf("\nmerge(arr,%d,%d,%d)\n",low,mid,high);
    merge(arr,low,mid,high);
  }
  return 0;
}

int merge(int arr[],int l,int m,int h)
{
  int arr1[10],arr2[10];  //crea dos arreglos temporales
  int n1,n2,i,j,k;
  //i es indice izq de arr1 con tamaño n1, j es indice der de arr2 con tamaño n2
  n1=m-l+1; //mid-low+1 = tamaño izquierdo
  n2=h-m; // tamaño derecho
  //lo que hace es ordenar los valores del arr en arr1 y arr2
  printf("Funcion Merge l:%d ,m:%d ,h:%d \n",l,m,h);
  printf("n1:%d ,n2:%d \n",n1,n2);
  for(i=0;i<n1;i++){
    arr1[i]=arr[l+i];
    printf("i arr1[%d]:%d = arr[%d]:%d\n",i,arr[i],l+i,arr[l+i]);
    for(j=0;j<n2;j++){
        arr2[j]=arr[m+j+1];
        printf("j arr2[%d]:%d= arr[%d]:%d\n",j,arr2[j],m+j+1,arr[m+j+1]);
    }
  }
  arr1[i]=9999;  
  printf("arr1[%d]:%d\n",i,arr1[i]);
  arr2[j]=9999;
  printf("arr2[%d]:%d \n",j,arr2[j]);
  //el final del arr1 y arr2 les pone 9999
  i=0;j=0;
  
  //compara y ordena el arreglo "combina"
  for(k=l;k<=h;k++)
  {
    printf("\nCombinando dos arrays: k:%d \n",k);
    printf("arr1[%d]:%d <= arr2[%d]:%d\n",i,arr1[i],j,arr2[j]);
    if(arr1[i]<=arr2[j]){
      arr[k]=arr1[i];
      printf("if arr[%d]:%d = arr1[%d]:%d \n",k,arr[k],i,arr1[i]);
      i++;
    }else{
      arr[k]=arr2[j];
      printf("else arr[%d]:%d = arr2[%d]:%d \n",k,arr[k],j,arr2[j]);
      j++;
    }
  }
  return 0;
}

Lorena Mosquera González

student•

Lo entendí mejor con tu código, muchas gracias! :)

Juan Manuel Otero Rey

student•

Mergesort en python:

''' Con esta funcion podemos crear arrays
    con un numero aletorio de datos'''
def create_array(size=10, max =50):
    from random import randint
    return [randint(0, max) for i in range(size)]

''' Rompemos el algoritmo en dos funciones principales
    la funcion principal mergesort y la propia funcion de merge
    para combinar los data sets '''
def merge(a, b):
    result=[]
    a_index, b_index = 0, 0

    ''' Itramaos mientras el indice del arreglo sea menor a su largo'''
    while a_index < len(a) and b_index < len(b):
        ''' Discriminamos que valor es mayor o menor y 
            lo almacenamos en result ordenado '''
        if a[a_index] < b[b_index]:
            result.append(a[a_index])
            ''' Aumentamos el indice para pasar al siguiente 
                valor dentro del array'''
            a_index += 1
        else:
            result.append(b[b_index])
            b_index += 1
    
    ''' Ahora verificamos que todos los elementos sean agregados.
        Utilizamos el metodo extend() para agregar todo elemento iterable
        de forma recursiva en el array que haya completado su ciclo primero '''
    
    if a_index == len(a):
        result.extend(b[b_index:])
    else:
        result.extend(a[a_index:])

    return result

def merge_sort(a):
    ''' Una lista con cero o un elementos
        esta ordenada por defecto '''
    if len(a) <= 1: return a

    ''' Rompemos al lista en dos partes left y right
        llamamos de forma recursiva a merge_sort() en cada mitad 
        aprovechando los slices de python '''
    left, right = merge_sort(a[:len(a)//2]), merge_sort(a[len(a)//2:])
    
    ''' Retornamos el resultado con la funcion merge() 
        de esta forma creamos la recursividad que realmente implementa nuestra logica '''
    return merge(left, right)

dataset = create_array()
print(merge_sort(dataset))

Juan Carlos Aranda Muñoz

student•

Así es como debió haber hecho el profesor, usar un lenguaje popular y básico acompañado de una buena explicación...

Luis Xavier Perez Miramontes

student•

Excelente, con este se entiende de mejor manera :D

Samar Jaffal

student•

Para poder entender el algoritmo y como se comporta cada función tuve que hacerlo a mano paso a paso con un simple array de 3 numeros = [3,2,1]. Me tomó un poco de tiempo para entender y 3 hojas de cuaderno jajaja

Efraín Hernández García

student•

Si la verdad fue algo complejo su estructuración

Ricardo Moreno

student•

Mi codigo de Merge Sort -> https://colab.research.google.com/drive/1H7WzH2AtZjKJbeoULSjKqjVeCaP8OdO3

procesó 100k datos en 0.89 [s] es una locura!!!!!!

Irving Jerico Hernandez Diaz

student•

muy buenos tus códigos

Ricardo Moreno

student•

@ijhd4k Gracias ;)

Victor Hugo Vázquez Gómez

student•

Hice éste tutorial de cómo comprendí Mergesort: https://platzi.com/tutoriales/1469-algoritmos/4260-merge-sort-en-java/

ariel alexander riaño soler

student•

gracias

Wandy Rafael Santana Evangelista

student•

Mege Sort en JS:

function merge(leftArr, rightArr) {
var sortedArr = [];
  while (leftArr.length && rightArr.length) {
    if (leftArr[0] <= rightArr[0]) {
      sortedArr.push(leftArr[0]);
      leftArr = leftArr.slice(1)
   } else {
      sortedArr.push(rightArr[0]);
      rightArr = rightArr.slice(1)
     }
   }
  while (leftArr.length)
    sortedArr.push(leftArr.shift());
  while (rightArr.length)
    sortedArr.push(rightArr.shift());
  return sortedArr;
}
function mergesort(arr) {
  if (arr.length < 2) {
    return arr; }
  else {
    var midpoint = parseInt(arr.length / 2);
    var leftArr   = arr.slice(0, midpoint);
    var rightArr  = arr.slice(midpoint, arr.length);
    return merge(mergesort(leftArr), mergesort(rightArr));
  }
}
let unsortedArr = [340, 1, 3, 3, 76, 23, 4, 12, 122, 7642, 646];
console.log('This should be the sorted array!')
console.log(mergesort(unsortedArr));```

Lucero Mendez

student•

En Js <3

<const mergeSort = arr => {
  //Check if the array has more than one element
  if (arr.length <= 1) {
    return arr;
  }
  //Figure out the middle of the array ( divide the array in half)
  let middle = Math.floor(arr.length / 2);
  //divided into left and right
  let left = arr.slice(0, middle);
  console.log("left", left);
  let right = arr.slice(middle);
  console.log("right", right);
  //using recursion to combine the left and right part

  return merge(mergeSort(left), mergeSort(right));
};

//Merge the two arrays: left and right
const merge = (leftArray, rightArray) => {
  let resultArray = [],
    leftIndex = 0,
    rightIndex = 0;

  //We willconcatenate values into the resultArray in order
  while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
    if (leftArray[leftIndex] < rightArray[rightIndex]) {
      resultArray.push(leftArray[leftIndex]);
      leftIndex++;
      console.log("leftArray", leftArray);
    } else {
      resultArray.push(rightArray[rightIndex]);
      rightIndex++;
      console.log("rightArray", rightArray);
    }
  }
  //Concate all the elements
  return resultArray
    .concat(leftArray.slice(leftIndex))
    .concat(rightArray.slice(rightIndex));
};

mergeSort([0, 3, 5, 2, 7, 1, -10, 3, 6]);>

Miqueas Gamero

student•

https://www.geeksforgeeks.org/merge-sort/ Yo había intentado resolver este algoritmo y esta fuente me ha sido de gran ayuda. A continuación, dejo mi implementación

#include <stdio.h>
#include <stdlib.h>

void merge (int array[], int left, int m, int right)
{
  int i, j, k;
  int n1 = m - left + 1;
  int n2 = right - m;

  int tempArray1[n1];
  int tempArray2[n2];

  for (i = 0; i < n1; i++)
  {
    tempArray1[i] = array[left + i];
  }
  for (j = 0; j < n2; j++)
  {
    tempArray2[j] = array[m + 1 + j];
  }

  i = 0;
  j = 0;
  k = left;

  while(i < n1 && j < n2)
  {
    if (tempArray1[i] <= tempArray2[j])
    {
      array[k] = tempArray1[i];
      i++;
    } else {
      array[k] = tempArray2[j];
      j++;
    }
    k++;
  }

  while(i < n1) {
    array[k] = tempArray1[i];
    i++;
    k++;
  }
  while(j < n2) {
    array[k] = tempArray2[j];
    j++;
    k++;
  }
  return 0;
}

void mergeSort (int array[], int left, int right)
{
  int m;
  if (left < right)
  {
    m = (left + right)/2;

    mergeSort(array, left, m);
    mergeSort(array, m+1, right);

    merge(array, left, m, right);
  }
  return 0;
}

void printArray(int array[], int right)
{
  int i;
  for(i = 0; i < right; i++)
  {
    printf("%d, ", array[i]);
  }
  return 0;
}

int main(int argc, char const *argv[]) {
  int array[] = {1, 10, 958, 95, 69, 35, 420};

  int sizeArray = sizeof(array)/sizeof(array[0]);

  printf("Array is \n");
  printArray(array, sizeArray);

  mergeSort(array, 0, sizeArray-1);

  printf("After merge sort algorithm\n");
  printArray(array, sizeArray);
  return 0;
}

Bernardo Aguayo Ortega

student•

Gracias Miqueas, me ayudo a comprender mejor

Diego Antonio Gomez Diaz

student•

Este algoritmo me tomo 5 dias en resolverlo y para ser honestos al 4to día mire la solución. Pero esto me ayudo a percatarme que estaba haciendo algo totalmente diferente a MergeSort.

Tambien vi el video que compartio nuestra compañera @DaneSanchz donde explica a profundidad como funciona este algoritmo (Link directo a su comentario). Esto me ayudo a entender mejor como funciona Merge Sort.

Después de analizar el algoritmo presentado en este artículo, me percate que este solo funciona con arreglos de 20 unidades que almacenan digitos menores a 9999 y el mismo solo puede ordenar ascedentemente.

Por el cual, me puse a pensar en una solución que atacara los problemas restantes. Despues de un día entero, les comparto la solución con C#:

Implementación: https://dotnetfiddle.net/xcHRq0

Código fuente:

using System;

namespace merge_sort
{
  public class MergeSort
  {
    public void Sort(ref int[] target, short order = 1)
    {
      InnerSort(ref target, order, 0, target.Length - 1);
    }

    private void InnerSort(ref int[] target, short order, int min, int max)
    {
      if (min < max)
      {
        int half = (min + max) / 2;
        InnerSort(ref target, order, min, half);
        InnerSort(ref target, order, half + 1, max);
        Merge(ref target, order, min, half, max);
      }
    }

    private void Merge(ref int[] target, int order, int min, int half, int max)
    {
      int value = 0;
      int? first = null, second = null;
      int[] temp = new int[max - min + 1];
      int firstIndex = min, secondIndex = half + 1;

      for (int index = 0; index < temp.Length; index++)
      {
        if (!first.HasValue && firstIndex <= half)
          first = target[firstIndex++];

        if (!second.HasValue && secondIndex <= max)
          second = target[secondIndex++];

        if (first.HasValue && second.HasValue)
        {
          if ((order == 1 && first > second) || (order == -1 && first < second))
          {
            value = second.Value;
            second = null;
          }
          else
          {
            value = first.Value;
            first = null;
          }
        }
        else
        {
          if (first.HasValue)
          {
            value = first.Value;
            first = null;
          }
          else
          {
            value = second.Value;
            second = null;
          }
        }

        temp[index] = value;
      }

      for (int index = 0; index < temp.Length; index++)
      {
        target[index + min] = temp[index];
      }
    }
  }
}

juan osuna

student•

Me costaba un poco entender el código, buscando un poco encontré este video, esta bastante bien explicado y me lo dejo mucho mas claro.

https://www.youtube.com/watch?v=ppNZ4bmrmGs

Youssef Abarca

student•

Algo complicado pero lo he logrado entender

Bernardo Aguayo Ortega

student•

me esta costando mucho jajaja, debo de buscar más info y practicarlo

Félix Andersson

student•

Yo lo implementé de esta manera en Javascript, quizá les sea mas fácil de entender

Y esta animación me ayudó a entenderlo

Efraín Hernández García

student•

Asi es como funciona el algoritmo graficamente: ![](

Franco Bottazzi

student•

En C o C++ (Acá aprovecho la equivalencia entre un puntero y un vector para hacer más simple el código, aunque entiendo que la forma de arriba es para quienes no estén familiarizados con los punteros):

template&lt;typename T&gt;
void mergeSort(T *v, unsigned int n) {
    //Caso base (ordeno un array si es de dos elementos o no hago nada si es uno)
    switch(n) {
        case 2:
            if(v[0] &gt; v[1])
                    changeValue(v[0], v[1]);
        case 1:
            return;
    }
    //recursión
    T *first = v, *second = v + n/2;
    mergeSort(first, n/2); //Primer mitad (n/2 primeros elementos)
    mergeSort(second, n - n/2); //Segunda mitad (el resto de los elementos)
    //merge
    T aux[n];
    for(unsigned int i = 0; i &lt; n; i++) {
        if( first == v + n/2 || (second != v + n &amp;&amp; *first &gt; *second))
            aux[i] = *(second++);
        else
            aux[i] = *(first++);
        
    }
    for(unsigned int i = 0; i &lt; n; i++)
        v[i] = aux[i];
}

import random

def mergeSort(arr):
  if len(arr) > 1:
    mid = len(arr) // 2
    left = arr[:mid]
    rigth = arr[mid:]
    print(f"Dividing left: {left} rigth {rigth}")

    mergeSort(left)
    mergeSort(rigth)
    # Esta es una de las dudas que me surgió al intentar entender recursividad.
    print("¿Cuándo se ejecuta esta línea?")

    i = 0
    j = 0
    k = 0

    while i < len(left) and j < len(rigth):
      if left[i] < rigth[j]:
        arr[k] = left[i]
        i += 1
      else:
        arr[k] = rigth[j]
        j += 1
      
      k += 1

    while i < len(left):
      arr[k] = left[i]
      i += 1
      k += 1 

    while j < len(rigth):
      arr[k] = rigth[j]
      j += 1
      k += 1 

    print(f'comparando izquierda {left}, derecha {rigth}')
    print(arr)
    print('-' *50)

  return arr


if __name__ == '__main__':
  n = int(input('What is the length of the array? '))

  arr = [random.randint(0, 100) for i in range(n)]
  print(arr)
  print('-' * 20)
  ordered_arr = mergeSort(arr)
  print(ordered_arr)

#include<stdio.h>
int main()
{
  int n,i,arr[20]; //declaracion array de 20 elementos
  printf("Enter the size of array: ");
  scanf("%d",&n); //valor del tamaño del array
  printf("Enter the elements:\n");
  for(i=0;i<n;i++){
    scanf("%d",&arr[i]);//ingresa los valores al arreglo
  }
  printf("merge_sort(arr,0,%d)\n",n-1);
  merge_sort(arr,0,n-1);  //aca ocurre la magia

  printf("Array Ordenado:");  //imprime arreglo ordenado
  for(i=0;i<n;i++)
    printf("%d,",arr[i]);

  return 0;
}

int merge_sort(int arr[],int low,int high)
{
  int mid;
  if(low<high)
  {
    mid=(low+high)/2;
   // Divide en 2 al array
    printf("ordena toda izquierda -> merge_sort(arr,%d,%d)\n",low,mid);
    merge_sort(arr,low,mid); //izquierda
    printf("ordena toda derecha -> merge_sort(arr,%d,%d)\n",mid+1,high);
    merge_sort(arr,mid+1,high); //derecha
   // Combina
    printf("\nmerge(arr,%d,%d,%d)\n",low,mid,high);
    merge(arr,low,mid,high);
  }
  return 0;
}

int merge(int arr[],int l,int m,int h)
{
  int arr1[10],arr2[10];  //crea dos arreglos temporales
  int n1,n2,i,j,k;
  //i es indice izq de arr1 con tamaño n1, j es indice der de arr2 con tamaño n2
  n1=m-l+1; //mid-low+1 = tamaño izquierdo
  n2=h-m; // tamaño derecho
  //lo que hace es ordenar los valores del arr en arr1 y arr2
  printf("Funcion Merge l:%d ,m:%d ,h:%d \n",l,m,h);
  printf("n1:%d ,n2:%d \n",n1,n2);
  for(i=0;i<n1;i++){
    arr1[i]=arr[l+i];
    printf("i arr1[%d]:%d = arr[%d]:%d\n",i,arr[i],l+i,arr[l+i]);
    for(j=0;j<n2;j++){
        arr2[j]=arr[m+j+1];
        printf("j arr2[%d]:%d= arr[%d]:%d\n",j,arr2[j],m+j+1,arr[m+j+1]);
    }
  }
  arr1[i]=9999;  
  printf("arr1[%d]:%d\n",i,arr1[i]);
  arr2[j]=9999;
  printf("arr2[%d]:%d \n",j,arr2[j]);
  //el final del arr1 y arr2 les pone 9999
  i=0;j=0;
  
  //compara y ordena el arreglo "combina"
  for(k=l;k<=h;k++)
  {
    printf("\nCombinando dos arrays: k:%d \n",k);
    printf("arr1[%d]:%d <= arr2[%d]:%d\n",i,arr1[i],j,arr2[j]);
    if(arr1[i]<=arr2[j]){
      arr[k]=arr1[i];
      printf("if arr[%d]:%d = arr1[%d]:%d \n",k,arr[k],i,arr1[i]);
      i++;
    }else{
      arr[k]=arr2[j];
      printf("else arr[%d]:%d = arr2[%d]:%d \n",k,arr[k],j,arr2[j]);
      j++;
    }
  }
  return 0;
}

''' Con esta funcion podemos crear arrays
    con un numero aletorio de datos'''
def create_array(size=10, max =50):
    from random import randint
    return [randint(0, max) for i in range(size)]

''' Rompemos el algoritmo en dos funciones principales
    la funcion principal mergesort y la propia funcion de merge
    para combinar los data sets '''
def merge(a, b):
    result=[]
    a_index, b_index = 0, 0

    ''' Itramaos mientras el indice del arreglo sea menor a su largo'''
    while a_index < len(a) and b_index < len(b):
        ''' Discriminamos que valor es mayor o menor y 
            lo almacenamos en result ordenado '''
        if a[a_index] < b[b_index]:
            result.append(a[a_index])
            ''' Aumentamos el indice para pasar al siguiente 
                valor dentro del array'''
            a_index += 1
        else:
            result.append(b[b_index])
            b_index += 1
    
    ''' Ahora verificamos que todos los elementos sean agregados.
        Utilizamos el metodo extend() para agregar todo elemento iterable
        de forma recursiva en el array que haya completado su ciclo primero '''
    
    if a_index == len(a):
        result.extend(b[b_index:])
    else:
        result.extend(a[a_index:])

    return result

def merge_sort(a):
    ''' Una lista con cero o un elementos
        esta ordenada por defecto '''
    if len(a) <= 1: return a

    ''' Rompemos al lista en dos partes left y right
        llamamos de forma recursiva a merge_sort() en cada mitad 
        aprovechando los slices de python '''
    left, right = merge_sort(a[:len(a)//2]), merge_sort(a[len(a)//2:])
    
    ''' Retornamos el resultado con la funcion merge() 
        de esta forma creamos la recursividad que realmente implementa nuestra logica '''
    return merge(left, right)

dataset = create_array()
print(merge_sort(dataset))

function merge(leftArr, rightArr) {
var sortedArr = [];
  while (leftArr.length && rightArr.length) {
    if (leftArr[0] <= rightArr[0]) {
      sortedArr.push(leftArr[0]);
      leftArr = leftArr.slice(1)
   } else {
      sortedArr.push(rightArr[0]);
      rightArr = rightArr.slice(1)
     }
   }
  while (leftArr.length)
    sortedArr.push(leftArr.shift());
  while (rightArr.length)
    sortedArr.push(rightArr.shift());
  return sortedArr;
}
function mergesort(arr) {
  if (arr.length < 2) {
    return arr; }
  else {
    var midpoint = parseInt(arr.length / 2);
    var leftArr   = arr.slice(0, midpoint);
    var rightArr  = arr.slice(midpoint, arr.length);
    return merge(mergesort(leftArr), mergesort(rightArr));
  }
}
let unsortedArr = [340, 1, 3, 3, 76, 23, 4, 12, 122, 7642, 646];
console.log('This should be the sorted array!')
console.log(mergesort(unsortedArr));```

<const mergeSort = arr => {
  //Check if the array has more than one element
  if (arr.length <= 1) {
    return arr;
  }
  //Figure out the middle of the array ( divide the array in half)
  let middle = Math.floor(arr.length / 2);
  //divided into left and right
  let left = arr.slice(0, middle);
  console.log("left", left);
  let right = arr.slice(middle);
  console.log("right", right);
  //using recursion to combine the left and right part

  return merge(mergeSort(left), mergeSort(right));
};

//Merge the two arrays: left and right
const merge = (leftArray, rightArray) => {
  let resultArray = [],
    leftIndex = 0,
    rightIndex = 0;

  //We willconcatenate values into the resultArray in order
  while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
    if (leftArray[leftIndex] < rightArray[rightIndex]) {
      resultArray.push(leftArray[leftIndex]);
      leftIndex++;
      console.log("leftArray", leftArray);
    } else {
      resultArray.push(rightArray[rightIndex]);
      rightIndex++;
      console.log("rightArray", rightArray);
    }
  }
  //Concate all the elements
  return resultArray
    .concat(leftArray.slice(leftIndex))
    .concat(rightArray.slice(rightIndex));
};

mergeSort([0, 3, 5, 2, 7, 1, -10, 3, 6]);>

#include <stdio.h>
#include <stdlib.h>

void merge (int array[], int left, int m, int right)
{
  int i, j, k;
  int n1 = m - left + 1;
  int n2 = right - m;

  int tempArray1[n1];
  int tempArray2[n2];

  for (i = 0; i < n1; i++)
  {
    tempArray1[i] = array[left + i];
  }
  for (j = 0; j < n2; j++)
  {
    tempArray2[j] = array[m + 1 + j];
  }

  i = 0;
  j = 0;
  k = left;

  while(i < n1 && j < n2)
  {
    if (tempArray1[i] <= tempArray2[j])
    {
      array[k] = tempArray1[i];
      i++;
    } else {
      array[k] = tempArray2[j];
      j++;
    }
    k++;
  }

  while(i < n1) {
    array[k] = tempArray1[i];
    i++;
    k++;
  }
  while(j < n2) {
    array[k] = tempArray2[j];
    j++;
    k++;
  }
  return 0;
}

void mergeSort (int array[], int left, int right)
{
  int m;
  if (left < right)
  {
    m = (left + right)/2;

    mergeSort(array, left, m);
    mergeSort(array, m+1, right);

    merge(array, left, m, right);
  }
  return 0;
}

void printArray(int array[], int right)
{
  int i;
  for(i = 0; i < right; i++)
  {
    printf("%d, ", array[i]);
  }
  return 0;
}

int main(int argc, char const *argv[]) {
  int array[] = {1, 10, 958, 95, 69, 35, 420};

  int sizeArray = sizeof(array)/sizeof(array[0]);

  printf("Array is \n");
  printArray(array, sizeArray);

  mergeSort(array, 0, sizeArray-1);

  printf("After merge sort algorithm\n");
  printArray(array, sizeArray);
  return 0;
}

using System;

namespace merge_sort
{
  public class MergeSort
  {
    public void Sort(ref int[] target, short order = 1)
    {
      InnerSort(ref target, order, 0, target.Length - 1);
    }

    private void InnerSort(ref int[] target, short order, int min, int max)
    {
      if (min < max)
      {
        int half = (min + max) / 2;
        InnerSort(ref target, order, min, half);
        InnerSort(ref target, order, half + 1, max);
        Merge(ref target, order, min, half, max);
      }
    }

    private void Merge(ref int[] target, int order, int min, int half, int max)
    {
      int value = 0;
      int? first = null, second = null;
      int[] temp = new int[max - min + 1];
      int firstIndex = min, secondIndex = half + 1;

      for (int index = 0; index < temp.Length; index++)
      {
        if (!first.HasValue && firstIndex <= half)
          first = target[firstIndex++];

        if (!second.HasValue && secondIndex <= max)
          second = target[secondIndex++];

        if (first.HasValue && second.HasValue)
        {
          if ((order == 1 && first > second) || (order == -1 && first < second))
          {
            value = second.Value;
            second = null;
          }
          else
          {
            value = first.Value;
            first = null;
          }
        }
        else
        {
          if (first.HasValue)
          {
            value = first.Value;
            first = null;
          }
          else
          {
            value = second.Value;
            second = null;
          }
        }

        temp[index] = value;
      }

      for (int index = 0; index < temp.Length; index++)
      {
        target[index + min] = temp[index];
      }
    }
  }
}

template&lt;typename T&gt;
void mergeSort(T *v, unsigned int n) {
    //Caso base (ordeno un array si es de dos elementos o no hago nada si es uno)
    switch(n) {
        case 2:
            if(v[0] &gt; v[1])
                    changeValue(v[0], v[1]);
        case 1:
            return;
    }
    //recursión
    T *first = v, *second = v + n/2;
    mergeSort(first, n/2); //Primer mitad (n/2 primeros elementos)
    mergeSort(second, n - n/2); //Segunda mitad (el resto de los elementos)
    //merge
    T aux[n];
    for(unsigned int i = 0; i &lt; n; i++) {
        if( first == v + n/2 || (second != v + n &amp;&amp; *first &gt; *second))
            aux[i] = *(second++);
        else
            aux[i] = *(first++);
        
    }
    for(unsigned int i = 0; i &lt; n; i++)
        v[i] = aux[i];
}

Bienvenido al Curso

Algoritmos y Estructuras de Datos: Curso Básico

Introducción a los algoritmos

Cómo Funcionan las Computadoras y el Sistema Binario

Introducción a Lenguajes de Programación: Bajo y Alto Nivel

Estructuras de Datos para Rutas Más Cortas en Mapas

Algoritmo de Dijkstra para encontrar la ruta más corta

Metodología para Resolver Algoritmos Paso a Paso

Variables y Tipos de Datos en Programación

Creación de Tipos de Datos Personalizados en C

Configuración de Ubuntu en Windows 10 para C/C++

Implementación de User Defined Data Type en C: Estructuras paso a paso

Tipos de Datos Abstractos y Estructuras de Datos en Programación

Tipos Abstractos de Datos: Lista, Pila, Cola y Diccionario

Tipos Abstractos de Datos: Listas, Pilas y Colas

Clases y objetos

Colas y estructuras de datos: gestión de pedidos en restaurante

Implementación de Queues con Arrays en Visual Studio Code

Implementación de Abstract Data Type en C: Función enqueue

Implementación de la función dequeue en estructuras de datos en C

Implementación de Colas en C: Declaración y Uso de Funciones Básicas

Algoritmos de ordenamiento

Algoritmos de Ordenamiento: Conceptos y Aplicaciones Básicas

Funcionamiento del Algoritmo de Ordenamiento Burbuja

Implementación de Bubble Sort en C paso a paso

Implementación de Bubble Sort en C y función de impresión

Ordenamiento por Inserción en C: Algoritmo y Ejemplo Práctico

Algoritmos de Ordenamiento Descendente: Implementación Práctica

Recursividad

Recursividad en Programación: Entendiendo el Factorial

Factorial Recursivo en C: Implementación y Ejemplo

Inversión de cadenas con recursividad en Java

Recursividad en Python: Arte con Turtle y Funciones Recursivas

Divide and conquer y programación dinámica

Diseño y análisis de algoritmos: Divide y vencerás

Introducción a Programación Dinámica y Quicksort