MergeSort

Video:
Merge-sort with Transylvanian-saxon (German) folk dance

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

https://youtu.be/TGRt7SQ1Xoc

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.

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)

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

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.

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

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;
}

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))

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

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

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

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

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));```

En Js ❤️

<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]);>

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;
}

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];
      }
    }
  }
}

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

Algo complicado pero lo he logrado entender

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

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<typename T>
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] > 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 < n; i++) {
        if( first == v + n/2 || (second != v + n && *first > *second))
            aux[i] = *(second++);
        else
            aux[i] = *(first++);
        
    }
    for(unsigned int i = 0; i < n; i++)
        v[i] = aux[i];
}

https://www.youtube.com/watch?v=xsmyLxbi-Kc this video right here is pretty good

Que paso con la clase, la explicación de este algoritmo y su implementación?

class MergeSort {
    private static void printArray (int [] array){

        for(int i: array) {
            System.out.print(i + "");
        }
        System.out.println();
    }

    private static int [] mergeSort(int [] array){

        if (array.length<=1) {

            return array;
            
        }
        int midpoint = array.length / 2;
        int [] left = new int [midpoint];
        int [] right;

        if(array.length % 2 ==0){
             right = new int [midpoint];
        }
        else{
            right = new int[midpoint+1];
        }

        for(int i = 0; i< midpoint; i++){

            left[i] = array[i];

        }

        for(int j = 0; j< right.length; j++){

            right[j] = array[midpoint+j];

        }

        int [] result = new int [array.length];

        left = mergeSort(left);
        right = mergeSort(right);

        result = merge(left, right);

        return result;
    }



    private static int [] merge(int [] left, int [] right){


        int [] result = new int[left.length + right.length];

        int leftPointer, rightPointer, resultPointer;
        leftPointer = rightPointer = resultPointer = 0;

        while(leftPointer < left.length || rightPointer< right.length){

            if (leftPointer<left.length && rightPointer <right.length) {
                
                if (left[leftPointer] < right[rightPointer]) {
                    result[resultPointer++] =left [leftPointer++];
                }else{
                    result[resultPointer++] = right[rightPointer];
                }
            }
            else if (leftPointer < left.length) {
                
                result[resultPointer++] = left[leftPointer++];

            }
            else if (rightPointer < right.length) {
                
                result[resultPointer++] = right[rightPointer++];

            }
        }

        return result;

    }

    public static void main(String[] args) {
        
        int [] array = { 5 , 4 , 3 , 2 , 1 };
        System.out.println("Initial Array:  ");
        printArray(array);

        array = mergeSort(array);
        System.out.println("Sorted Array:  ");
        printArray(array);

    }
}

en Java

Para complementar esta clase, les recomiendo este vídeo, que en mi opinión esta excelentemente explicado;

Merge Sort in Python Programming | Program | Detailed Explanation

Esta fue mi implementación del merge sort con python

def merge_sort(array, low, high):

    arrB = []
    arrC = []
    mid = (low+high) / 2
    
    if len(array) == 1:
        return array
    else:
        
        for i in range(low,int(mid)):
            arrB.append(array[i])

        for i in range((int(mid)), high):
            arrC.append(array[i])

        sortedArray = merge(merge_sort(arrB,low, len(arrB)), merge_sort(arrC, low, len(arrC)))
        return sortedArray

def merge(arr1, arr2):
    
    i = 0
    k = 0
    c = 0
    arrS = []

    while c < (len(arr1) + len(arr2)):
        if i >= len(arr1):
            arrS.append(arr2[k])
            k += 1
        elif k >= len(arr2):
            arrS.append(arr1[i])
        else:
            if arr1[i] < arr2[k]:
                arrS.append(int(arr1[i]))
                i += 1
            else:
                arrS.append(int(arr2[k]))
                k += 1
        c += 1

    return list(arrS)

def run():
    array = []
    print("Ingrese el tamaño del arreglo: ")
    n = int(input())
    print("Ingrese los valores: ")
    for i in range(0,n):
        array.append(int(input()))
    print("Su arreglo inicial es de: " + str(array))
    finalArray = merge_sort(array, 0, n)
    print("El arreglo ordenado de forma ascendente es: " + str(finalArray))


if __name__ == "__main__":
    run()```

Les comparto este vídeo que encontré por si quieren profundizar más en el funcionamiento del merge sort.

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

Difícil al principio, pero luego de invertirle varias horas se entiende.

JS

const merge = (arrA,arrB) =>{
    let singleSorted = []
    while (arrA.length && arrB.length){
        if (arrA [0] < arrB[0]){
            singleSorted.push(arrA[0])
            arrA.shift()
        } else {
            singleSorted.push(arrB[0])
            arrB.shift()
        }
    }
    return singleSorted.concat(arrA,arrB)
}

const mergeSort = arr => {
    if (arr.length < 2){
        return arr
    }
    let midPoint = Math.floor(arr.length / 2)
    let left = mergeSort(arr.slice(0, midPoint))
    let right = mergeSort(arr.slice(midPoint))
    return merge(left, right)
}
console.log(mergeSort([0,3,5,2,7,1,-10,3,6,1,7,19,30,-100,0, .5]))```

Hice unas mejorar al código para que se viera mejor la salida:

//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 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;
}
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 main()
{
  int n,i;
  
  printf("Enter the size of array: ");  // input the elements
  scanf("%d",&n);
  for(i=0;i<n;i++) {
    printf("Element [%d]: ", 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;
}

el codigo es complejo de entender me parece mas facil en pyhton

Estoy de acuerdo con lo que algunos dicen, este código merece ser explicado. Me tomó como 3H entenderlo y saber cómo yo mismo puedo programar un merge_sort. Pero por otro lado tambn ps acá se evidencia el deseo que cada uno tiene por aprender, que al ser así (aprendiendo ("de verdad y honestamente contigo mismo) autonomamente) de hecho se aprende más. Si, me tomó como 3H pero ahora entiendo super bien este algoritmo.
 
Comparto con ustedes mi código (en JS):

function merge_sort(arr, mid = arr.length/2) {
  if (arr.length<2) {
    return arr
  }
  const left = arr.splice(0, mid)
  return merge(merge_sort(left), merge_sort(arr))
}

function merge(arrLeft, arrRight) {
  let sort_array = []
  while (arrLeft.length && arrRight.length) {
    if (arrLeft[0] < arrRight[0]) {
      sort_array.push(arrLeft.shift())
      sort_array.push(arrRight.shift())
    }
    else {
      sort_array.push(arrRight.shift())
      sort_array.push(arrLeft.shift())
    }
  }
  return [...sort_array]
}

let array = [8, 2, 7, 3, 23, 50, 0, 1]
console.log(`\n-FINAL: ${merge_sort(array)}- - -`);

function mergesort(array){
    if(array.length == 1){
        return array;
    }

    let n = array.length;
    let m =  Math.ceil(n/2);
    let array1 = [];
    let array2 = [];

    for(let i=0; i<m; i++){
        array1.push(array.shift());
    }
    for(let i=m; i<n; i++){
        array2.push(array.shift());
    }

    array1 = mergesort(array1);
    array2 = mergesort(array2);

    return merge(array1, array2);
}

function merge(array1, array2){
    let merged_array = [];

    while(array1.length && array2.length){
        if(array1[0]<array2[0]){
            merged_array.push(array1.shift());
        }else{
            merged_array.push(array2.shift());
        }
    }
    while(array1.length){
        merged_array.push(array1.shift());
    }
    while(array2.length){
        merged_array.push(array2.shift());
    }
    
    return merged_array;
}

let nums = [38,27,43,3,9,82,10];
nums = mergesort(nums);
console.log(nums);

Explicación con Python

• This code uses the merge sort algorithm to sort an array of integers. The algorithm works by dividing the array into two smaller subarrays, sorting each subarray recursively, and then merging the two sorted subarrays back into the original array. This process is repeated until the entire array is sorted.

• In this Python version of the code, we define a merge_sort function that takes an array as an input. The function first checks if the length of the array is greater than one. If it is, it finds the middle index of the array using integer division (//). The array is then divided into two subarrays using slicing ([:mid] and [mid:]). The merge_sort function is then called recursively on each subarray to sort them.

• Once both subarrays are sorted, we use a while loop to merge them back into the original array. We use three indices i, j, and k to keep track of our position in the left subarray, right subarray, and original array respectively. We compare elements from both subarrays and insert the smaller element into the original array. We continue this process until we have inserted all elements from both subarrays back into the original array.

• Finally, we have two more while loops to copy any remaining elements from either subarray back into the original array. This is necessary because one of the subarrays may have more elements than the other.

• At the end of this code snippet, we test our merge_sort function on an example array. We print out both the original and sorted arrays to verify that our function works correctly.

# Merge Sort in Python

def merge_sort(arr):
    # If the array has more than one element
    if len(arr) > 1:
        # Find the middle index of the array
        mid = len(arr) // 2
        print('mid:', mid)
        # Divide the array into two subarrays using the middle index
        left_half = arr[:mid]
        print('Left Half:' , left_half)
        right_half = arr[mid:]
        print('Right Half:', right_half)

        # Recursively sort the left and right subarrays
        merge_sort(left_half)
        merge_sort(right_half)

        # Merge the two sorted subarrays into the original array
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
            print('Merge two sorted subarays \n')
            print('i:', left_half, ' j:', right_half, ' k:', arr)

        # Copy any remaining elements of the left subarray into the original array
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
            print('copy remaining elements of the left \n')
            print('i:', left_half, ' j:', right_half, ' k:', arr)

        # Copy any remaining elements of the right subarray into the original array
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
            print('copy remaining elements of the right \n')
            print('i:', left_half, ' j:', right_half, ' k:', arr)


# Test the merge_sort function
arr = [12, 11, 13, 5, 6, 7]
print("Original array:", arr)
merge_sort(arr)
print("Sorted array:", arr)

Output:

Original array: [12, 11, 13, 5, 6, 7]
mid: 3
Left Half: [12, 11, 13]
Right Half: [5, 6, 7]
mid: 1
Left Half: [12]
Right Half: [11, 13]
mid: 1
Left Half: [11]
Right Half: [13]
Merge two sorted subarays

i: [11] j: [13] k: [11, 13]
copy remaining elements of the right

i: [11] j: [13] k: [11, 13]
Merge two sorted subarays

i: [12] j: [11, 13] k: [11, 11, 13]
Merge two sorted subarays

i: [12] j: [11, 13] k: [11, 12, 13]
copy remaining elements of the right

i: [12] j: [11, 13] k: [11, 12, 13]
mid: 1
Left Half: [5]
Right Half: [6, 7]
mid: 1
Left Half: [6]
Right Half: [7]
Merge two sorted subarays

i: [6] j: [7] k: [6, 7]
copy remaining elements of the right

i: [6] j: [7] k: [6, 7]
Merge two sorted subarays

i: [5] j: [6, 7] k: [5, 6, 7]
copy remaining elements of the right

i: [5] j: [6, 7] k: [5, 6, 7]
copy remaining elements of the right

i: [5] j: [6, 7] k: [5, 6, 7]
Merge two sorted subarays

i: [11, 12, 13] j: [5, 6, 7] k: [5, 11, 13, 5, 6, 7]
Merge two sorted subarays

i: [11, 12, 13] j: [5, 6, 7] k: [5, 6, 13, 5, 6, 7]
Merge two sorted subarays

i: [11, 12, 13] j: [5, 6, 7] k: [5, 6, 7, 5, 6, 7]
copy remaining elements of the left

i: [11, 12, 13] j: [5, 6, 7] k: [5, 6, 7, 11, 6, 7]
copy remaining elements of the left

i: [11, 12, 13] j: [5, 6, 7] k: [5, 6, 7, 11, 12, 7]
copy remaining elements of the left

i: [11, 12, 13] j: [5, 6, 7] k: [5, 6, 7, 11, 12, 13]
Sorted array: [5, 6, 7, 11, 12, 13]

Que haría sin GPT. El curso debería llamarse “Teorico” para que tu practiques por tu cuenta.

https://www.youtube.com/watch?v=5Z9dn2WTg9o
Les dejo otro ejemplo del proceso de ordenamiento.

Para entender el algoritmo me sirvió el debug con python, espero que puedan agregar algo similar si actualizan el curso, una explicación paso a paso del proceso de debug estaría bueno!

Continuando con los aportes, este video me pareció genial para comprender el algoritmo de ordenamiento merge sort.

Lo hice con Python:

def merge_sort(lista):
    if len(lista) > 1:
        half = len(lista) // 2
        first_half = lista[:half]
        second_half = lista[half:]

        merge_sort(first_half)
        merge_sort(second_half)
        n = 0
        m = 0
        p = 0

        while n < len(first_half) and m < len(second_half):
            if first_half[n] > second_half[m]:
                lista[p] = first_half[n]
                n += 1
            else:
                lista[p] = second_half[m]
                m += 1
            p += 1

        while n < len(first_half):
            lista[p] = first_half[n]
            n += 1
            p += 1

        while m < len(second_half):
            lista[p] = second_half[m]
            m += 1
            p += 1

numeros = [100, 1, 5, 10, 8, 35, 21, 19, 81]

print(numeros)

merge_sort(numeros)
print(numeros)

Tengo una pregunta, al momento de hallar el primer valor de mid la ecuación sería:

mid = (0 + 9) / 2 = 4.5 (Reemplazando los índices)
Yo esperaría que aproximara el valor de mid a mid = 5, pero con este pequeño código en C me demuestra que toma el valor de 4, ¿Saben por qué?

#include<stdio.h>

int main(int argc, char const *argv[])
{
    int med = (9 + 0) / 2;
    printf("Numero medio %d", med);
    return 0;
}

Ok voy a leer sobre el algoritmo y luego interpretar este código.

Implementación en C.

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


void merge(int array[], int head, int mid, int rear)
{
	int l = head;  // left index
	int r = mid + 1;  // right index
	int i = head;  // tmp index
	int tmp[rear];  // array to temporarily store values from array[] parameter

	/* Copy and sort the values between head | mid & mid + 1 | rear from array */
	while (l <= mid && r <= rear)
	{
		if (array[l] <= array[r])
			tmp[i++] = array[l++];
		else
			tmp[i++] = array[r++];
	}

	/* Copy remaining elements */
	while (l <= mid)
		tmp[i++] = array[l++];
	while (r <= rear)
		tmp[i++] = array[r++];

	/* Overwrite array elements with tmp elements */
	for (i = head; i <= rear; i++)
		array[i] = tmp[i];
}

void mergeSort(int array[], int head, int rear)
{
	if (head < rear)
	{
		/* Get the index of the middle of the array and call recursively
		 * the function */
		int mid = (head + rear) / 2;
		mergeSort(array, head, mid);
		mergeSort(array, mid + 1, rear);
		merge(array, head, mid, rear);
	}
}

void showArray(int array[], size_t n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d, ", array[i]);
	}
	printf("\n\n\n");
}

void main(const int argc, char argv[])
{
	printf("Merge Sort:\n");
	int a[] = {-796, 3229, -5164, -362, 4408, 8965, -6068, 9329, -3034, -443, -6693,  9497, 2615, -5966, -9065,
	-1160, 6148, 5517, 1123, -8887, 5649, 3302, -1176, -8542, -9166, 8, -2906, 8987, -2414, -7984, 4410,
	8872, 5241, -4556, 59, -5562, -3877, 7452, -4467, 2076, 4076, 4297, -3847, -2055, 4483, -1484, -2371,
	6199, -7261, -7032, 6010, 2325, -6625, -2601, 3870, 1822, -5665, 9622, 9883, -5794, -5218, 2926,
	8599, -3099, 6399, -2570, 3943, -2409, 5114, 9791, -4420, 1065, 3077, -1062, -8004, 4397, 1635, 8578,
	-9226, 9222, -1793, -26915, -5060, -4727, -4098, 946, -6558, -4111, 4575, -2685, -4729, -5277, 1936,
	5106, -2089, 824, 9421, -1683, -2083, 7891, -2099, 1305, -9076, -3535, 2565, -2871, 9448, 7177, -8614,
	-9954, -362, 1455, -8834, -9846, -8412, 1175, -1981, -5991, 7201, -1997, -5156, -1634, -9803, 1032,
	9551, -6153, 8502, 3536, -2980, 8681, -9210, 4408, 8780, -916, -369, -8651, 1246, -702, -5555, 23,
	8208, 2037, 6941, 9545, -5147, 5063, -8358, 2772, 8553, 9885, 4624, -3576, 9131, 1229, -429, -479,
	-673, -7060, -4031, 5650, 6679, 6796, 5622, -6256, -238, -6096, 3096, -1610, -2948, 6291, -1666, 5219,
	5850, 7387, -3260, 3672, -1766, -9941, 8252, 2649, 7079, -8026, 6356, 676, -5065, -6338, 3287, 680,
	-3269, 2770, 6637, -8744, 9162, -2204, -3066, -7228, 8762, 1505, 4957, 766, -9136, 4632, -5022, -9999,
	5361, 2732, 7831, -501, -4650, 7236, 3682, -2438, 5574, -8230, -9669, -7442, 7966, -2905, 7629, 7137,
	200, -8670, -749, 2228, 458, 7889, -3668, -5350, -3261, 6741, -6953, 4800, 3372, 6662, -1018, 8523,
	3164, 3577, 9720, -6826, -1574, -7875, -2796, -1078, -4755, 4926, 3368, 4302, 9254, 6410, -4689, 7878,
	2461, 8233, -6688, 5904, 4735, -2940, 8830, 9976, -3674, 4222, -1446, 6187, -3181, -8882, 5487, -6939,
	-7885, 3786, -6234, -1062, -4553, -5709, 8459, 5008, 3352, 6586, 537, -7610, 3261, 8246, -2105, 5107,
	7957, -7886, -2925, -2541, -7449, 9521, 5073, -239, -8054, -4379, -8323, -6485, -4828, -5294, -2720, 595};
	size_t size = sizeof(a)/sizeof(a[0]);
	showArray(a, size);
	mergeSort(a, 0, (int)size - 1);
	showArray(a, size);
	return 0;
}

/**
 * Mergesort es un algoritmo tipo Divide y Vencerás. Divide el array ingresado en
 * dos mitades, se llama a sí mismo para las dos mitades y después une las dos
 * mitades ordenadas. La función merge() es usada para unir las dos mitades.
 * El merge(arr,l,m,r) es un proceso clave que asume que arr[l..m] y arr[m+1..r]
 * están ordenados y une las dos mitades en uno.
 *
 * Pasos a seguir:
 *
 * MergeSort(arr[], l, r)
 * if r > 1
 *
 * 1. Encuentra el punto medio para dividir el array en dos mitades:
 *              middle m = (1+r) / 2
 * 2. Llama a mergeSort para la primera mitad:
 *              Llama a mergeSort(arr, l, m)
 * 3. Llama a mergeSort para la segunda mitad:
 *              Llama a mergeSort(arr, m+1, r)
 * 4. Une las dos mitades ordenadas en el paso 2 y 3:
 *              Llama a merge(arr, l, m, r)
 * */
public class MergeSort {
    public void merge(int arr[], int left, int middle, int right) {
        //Encuentra el tamaño de los dos sub-arrays para unirlos.
        int n1 = middle - left + 1;
        int n2 = right - middle;

        //Arrays temporales.
        int leftArray[] = new int [n1];
        int rightArray[] = new int [n2];

        //Copia los datos a los arrays temporales.
        for (int i=0; i<n1; i++) {
            leftArray[i] = arr[left + i];
        }
        for (int j=0; j<n2; j++) {
            rightArray[j] = arr[middle+ j + 1];
        }

        //Une los arrays temporales.

        //Índices inicial del primer y segundo sub-array.
        int i = 0, j = 0;

        //Índice inicial del sub-array.
        int k = left;

        //Ordenamiento.
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        /* Copiar los elementos restantes de leftArray[] */
        while (i < n1)
        {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        /* Copiar los elementos restantes de rightArray[] */
        while (j < n2)
        {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    /**
     * Función principal que ordena el array usando merge.
     * */
    public void sort(int arr[], int left, int right) {
        if (left < right) {
            //Encontrar el punto medio.
            int middle = (left+right) / 2;

            //Ordena la primera y segunda mitad.
            sort(arr, left, middle);
            sort(arr, middle+1, right);

            //Une las mitades ordenadas.
            merge(arr, left, middle, right);

        }
    }

    /**
     * Función de utilidad para imprimir el array de tamaño n.
     * */
    public void printArray(int arr[]) {
        int n = arr.length;
        for (int i=0; i<n; ++i) {
            System.out.println(arr[i] + " ");
        }
        System.out.println();
    }
}

Me confundi un poco por las variables.

//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;
}

aqui hya una explicacion

https://www.youtube.com/watch?v=55d8cAK9oE0

Hice el código para entenderlo un poco mejor, es bastante complejo pero no imposible de entender; igualmente comparto el link de mis otros compañeros que me ayudaron a entender.

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

int main()
{
    int arreglo[20];
    int tam;
    //Se ingresa el tamaño del arreglo
    printf("Ingrese el tamaño del arreglo: ");
    scanf("%i", &tam);

    //Se ingresan los valores del arreglo
    printf("Ingrese los %i valores del arreglo: ", tam);
    for(int i=0; i<tam; i++)
    {
        scanf("%i", &arreglo[i]);
    }
    //Se imprimen lo valores del arreglo
    int i = 0;
    printf("Los valores del arreglo son: [");
    while(i<tam)
    {
        printf("%i,", arreglo[i]);
        i++;
    }
    printf("] \n");

    //Se realiza el proceso de merge, donde se Divide, Ordena y Combina.
    merge_sort(arreglo, 0, tam-1);

    //Se realiza la impresion del arreglo ordenado
    printf("El arreglo ordenado queda de la soguiente manera: [");
     for(i=0;i<tam;i++)
         printf("%d, ",arreglo[i]);
    printf("] \n");

    return 0;
}


int merge_sort(int arreglo[], int low, int high)
{
    int mid;

    if(low<high)
    {
        //Se escoge una mitad del arreglo
        mid = (low+high)/2;
        //Divide et Impera
        merge_sort(arreglo,low,mid);
        merge_sort(arreglo,mid+1,high);
        //Combina
        merge(arreglo,low,mid,high);
    }
    
    return 0;
}

int merge(int arreglo[], int l, int m, int h)
{
    //Las ds divisiones realizadas por los merge. Se dividiran en estos dos arreglos.
    int arr1[10];
    int arr2[10];
    int n1, n2, i, j, k;
    //a traves de estos calculos se establecen los limetes para cada arreglo.
    n1 = m-l+1;
    n2 = h-m;
    //Los limetes establicidos nos ayudaran a ordenar los números establecidos en cada arreglo.
    //Se ordenan los números.
    for(i=0; i<n1; i++)
        arr1[i] = arreglo[l+i];
    
    for(j=0; j<n2; j++)
        arr2[j] = arreglo[m+j+1];
    //Las siguientes lineas establencen el limite del final de cada arreglo
    arr1[i] = 9999;
    arr2[i] = 9999;
    //Se reinician los valores de I y J
    i=0;
    j=0;
    // El siguiente ciclo, se encargará de combinar los dos arreglos. llegando asi a la fase final del algoritmo
    for(k=0; k<=h; k++)
    {
        if(arr1[i] <= arr2[j])
            arreglo[k] = arr1[i++];
        else
            arreglo[k] = arr2[j++];
    }
    return 0;
}```

https://www.youtube.com/watch?v=XaqR3G_NVoo
https://platzi.com/tutoriales/1469-algoritmos/4260-merge-sort-en-java/

Hola, sé que este algoritmo es un poco complicado, así que les dejo una pequeña explicación, espero que les sea de utilidad. Esta es mi implementación dinámica en C, la cual usa números aleatorios:

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

void print_vector(int *vector, int lon);
int count_char(int N);
void MergeSort(int * vector, int lon);
void merge(int *left, int left_size, int *right, int right_size, int *vector);

int main(int *argc, int **argv){
    srand(time(0));
    int lon = rand() % 101 + 999;
    printf("%d\n", lon);
    int *vector = (int*)calloc(lon, sizeof(int));

    for(int i = 0; i < lon; i++){
        *(vector + i) = rand() % 10000 + 1;
        // printf("%d\t%d\n", vector[i],count_char(vector[i]));
    }
    // printf("\n");
    print_vector(vector, lon);
    MergeSort(vector, lon);
    print_vector(vector, lon);

    return 0;
}

void MergeSort(int *vector, int lon){
    int mid = lon/2;
    if (lon < 2) return;
    int *left = (int*)calloc(mid, sizeof(int));
    int *right = (int*)calloc(lon - mid, sizeof(int));

    //Slicing arrays in C
    memcpy(left, vector, mid*sizeof(int));
    memcpy(right, vector+mid, (lon - mid)*sizeof(int));
    MergeSort(left, mid);
    MergeSort(right, lon-mid);
    merge(left, mid, right, lon - mid, vector);
    // print_vector(left, mid);
    // print_vector(right, lon-mid);
}

void merge(int *left, int left_size, int *right, int right_size, int *vector){
    int i, j, k;
    i = j = k = 0;
    while(i < left_size && j < right_size){
        if(left[i] <= right[j]){
            vector[k] = left[i];
            i++;
        }else{
            vector[k] = right[j];
            j++;
        }
        k++;
    }
    while(i < left_size){
        vector[k] = left[i];
        i++;
        k++;
    }
    while(j < right_size){
        vector[k] = right[j];
        j++;
        k++;
    }
}

void print_vector(int *vector, int lon){
    char *str = (char*)calloc(1, sizeof(char));
    char *str_aux = 0;
    int str_size = 1;
    str[0] = '[';

    // printf("Salida de print_vector\n");
    for(int i = 0; i < lon; i++){
        str_size += count_char(vector[i]) + 3;

        // printf("i: %d\tstr_size: %d\tvector[%d]: %d\n", i, str_size, i, vector[i]);

        str_aux = (char *)realloc(str, sizeof(char)*str_size);
        if(str_aux != 0){
            str = str_aux;
        }else{
            printf("Error\n");
            return;
        }
        if(i != lon - 1){
            sprintf(str + strlen(str), "%d, ", vector[i]);
        }else{
            sprintf(str + strlen(str), "%d]", vector[i]);
        }
        // printf("%s\n", str);
    }
    
    printf("%s\n", str);
}

int count_char(int N){
    int numbers = 0;
    if(N < 0){
        numbers++;
        N *= -1;
    }
    while(N > 0){
        numbers++;
        N /= 10;
    }
    return numbers;
}```

No entiendo el funcionamiento de esto, y traté de realizar el código con un arreglo de 2 posiciones y no tiene sentido, no sé que estoy haciendo mal.

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

// Divide:
// Conquer:
// Combine:
#include<stdio.h>
int arr[20];

int merge(int arr[],int l,int m,int h)
{
  int arr1[10], arr2[10];
  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;
  arr2[j]=9999;

  i=0; j=0;
  for (size_t k = l; k <= h; k++)
  {
    if (arr1[i]<=arr2[j])
      arr[k]=arr1[i++];
    else
      arr[k]=arr2[j++];
  }

  return 0;
}

int merge_sort(int arr[],int low,int high)
{
  int mid;
  if (low<high)
  {
    mid=(low+high)/2;
    merge_sort(arr,low,mid);
    merge_sort(arr,mid+1,high);
    merge(arr, low,mid,high);
  }

  return 0;
}

int main()
{
  int n,i;

  printf("Enter the size of array\n");
  scanf("%d",&n);
  printf("Enter the elements:");
  for (i=0;i<n;i++)
    scanf("%d",&arr[i]);

  merge_sort(arr,0,n-1);

  printf("Sorted array:");
  for (i=0;i<n;i++)
    printf("%d",arr[i]);

  return 0;
}

No entiendo el código 😭

A pesar de que me quedaron ciertas dudas, este código es mucho mejor para aprender la función:

#include <stdio.h>


// Merges two subarrays of arr[]. 
// First subarray is arr[l..m] 
// Second subarray is arr[m+1..r] 
void merge(int arr[], int l, int m, int r) 
{ 
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
  
    /* create temp arrays */
    int L[n1], R[n2]; 
  
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        R[j] = arr[m + 1+ j]; 
  
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray 
    j = 0; // Initial index of second subarray 
    k = l; // Initial index of merged subarray 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    /* Copy the remaining elements of L[], if there 
       are any */
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    /* Copy the remaining elements of R[], if there 
       are any */
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 

/* l is for left index and r is right index of the 
   sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
        // Same as (l+r)/2, but avoids overflow for 
        // large l and h 
        int m = l+(r-l)/2; 
  
        // Sort first and second halves 
        mergeSort(arr, l, m); 
        mergeSort(arr, m+1, r); 
  
        merge(arr, l, m, r); 
    } 
    return;
} 

int main()
{

    int arr[] = {2,58,3,56,23,8,3};
    int high = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, high-1);

    for(int i = 0; i < high; i++)
    {
        printf("%d \n", arr[i]);
    }


    return 0;
}

Mi solución para C#

    /// <summary>
    /// La clase MergeSort contiene las funciones que abarcan los temas tratados en la clase numero 32 del Curso Basico de Algoritmos de Platzi.
    /// </summary>
    class MergeSort
    {

        /// <summary>
        ///  Función para ordenar los elementos de dos arrays y unirlos recursivamente utilizando Merge Sort.
        /// </summary>
        /// <param name="p_array_izquierdo"> El array izquierdo.</param>
        /// <param name="p_array_derecho"> El array derecho.</param>
        /// <returns>La fusion de ambos arrays.</returns>
        public static int [] Merge( int [] p_array_izquierdo, int [] p_array_derecho )
        {

            // Se establece la longitud total del array resultado con la suma de la longitud de los dos arrays.
            //  [ Cantidad de elementos del array izquierdo ] + [ Cantidad de elementos del array derecho ]

            int longitud_resultado = p_array_izquierdo.Length + p_array_derecho.Length;

            // Se inicializa el Array que fusionara ambos Arrays
            int [] p_array_resultado = new int[longitud_resultado];

            // Se inician tres variables que actuaran como indices para recorrer los Arrays
            int indice_array_izquierdo = 0, indice_array_derecho = 0, indice_array_resultado = 0;

            // Mientras que cada array tenga elementos
            while ( indice_array_izquierdo < p_array_izquierdo.Length || indice_array_derecho < p_array_derecho.Length) {

                // Si ambos arrays tienen elementos
                if (indice_array_izquierdo < p_array_izquierdo.Length && indice_array_derecho < p_array_derecho.Length)
                {
                    // Si un elemento en el array izquierdo es menor que el que contiene el array derecho
                    // El elemento del array izquierdo se añadira al resultado.
                    if (p_array_izquierdo[indice_array_izquierdo] <= p_array_derecho[indice_array_derecho])
                    {
                        p_array_resultado[indice_array_resultado] = p_array_izquierdo[indice_array_izquierdo];
                        indice_array_izquierdo++;
                        indice_array_resultado++;

                    }
                    // En caso contrario el que se añadira es el elemento del array derecho
                    else
                    {
                        p_array_resultado[indice_array_resultado] = p_array_derecho[indice_array_derecho];
                        indice_array_derecho++;
                        indice_array_resultado++;

                    }// Fin de: if (p_array_izquierdo[indice_array_izquierdo] <= p_array_derecho[indice_array_derecho])

                }// Fin de: if (indice_array_izquierdo < p_array_izquierdo.Length && indice_array_derecho < p_array_derecho.Length)

                // Si solo p_array_izquierdo array tiene elementos todos se añaden al resultado.
                else if (indice_array_izquierdo < p_array_izquierdo.Length)
                {
                    p_array_resultado[indice_array_resultado] = p_array_izquierdo[indice_array_izquierdo];
                    indice_array_izquierdo++;
                    indice_array_resultado++;
                }
                // Si solo p_array_izquierdo array tiene elementos todos se añaden al resultado.
                else if (indice_array_derecho < p_array_derecho.Length)
                {
                    p_array_resultado[indice_array_resultado] = p_array_derecho[indice_array_derecho];
                    indice_array_derecho++;
                    indice_array_resultado++;
                }


            }// while ( indice_array_izquierdo < p_array_izquierdo.Length || indice_array_derecho < p_array_derecho.Length) { 


            return p_array_resultado;

        }// Fin de: public static int [] Merge( int [] p_array_izquierdo, int [] p_array_derecho )

        /// <summary>
        /// Función que toma un array de int con los elementos desordenados y los ordena dividiendolo en dos partes recursivamente.
        /// </summary>
        /// <param name="p_array_entrada"></param>
        /// <returns>Un array con los elementos ordenados usando Merge Sort</returns>
        public static int[] Merge_Sort( int[] p_array_entrada ) 
        {

            int[] p_array_izquierdo;
            int[] p_array_derecho;
            int[] p_array_resultado = new int[p_array_entrada.Length];
            
            
            // Al ser una función recursiva se realiza esta verificación para evitar errores.
            // Si el array tiene un tamaño de 1 o menor no tiene sentido ordenarlo.
            if (p_array_entrada.Length <= 1)
                return p_array_entrada;
            
            // El punto medio del array de entrada se utiliza para dividir el array en dos partes
            int punto_medio = p_array_entrada.Length / 2;

            // Se divide el p_array de entrada en dos. Uno que llamaremos izquierdo y el otro derecho.
            //            ----------[ Array Entrada ]----------
            //            |                                   |
            //   [ Array Izquierdo ]                   [ Array Derecho ]
            //
            
            // Se crea el array izquierdo utilizando como longitud el punto medio del array de entrada
            p_array_izquierdo = new int[ punto_medio ];

            // Si el array de entrada contiene un numero par de elementos, tanto el array izquierdo como el derecho tendran el mismo numero de elementos.
            if ( p_array_entrada.Length % 2 == 0 )
            {
                p_array_derecho = new int[punto_medio];
            }
            else // En caso contrario contendra un numero impar por lo que el array derecho contendra un elemento mas que el array izquierdo.
            {
                p_array_derecho = new int[punto_medio + 1];
            }

            //Se carga el array izquierdo con los elementos que contiene el array de entrada hasta su punto medio
            for ( int i = 0; i < punto_medio; i++ )
            {
                p_array_izquierdo[i] = p_array_entrada[i];
            }
            
            //Se crea una variable auxiliar para cargar los elementos restantes al array derecho   
            int aux = 0;
            
            // Se inicia la carga desde el valor de punto medio debido a que cargamos los anteriores elementos en el array izquierdo
            for (int i = punto_medio; i < p_array_entrada.Length; i++)
            {
                p_array_derecho[aux] = p_array_entrada[i];
                aux++;
            }
            
            // Se ordenan recursivamente los elementos que contiene el array izquierdo.
            p_array_izquierdo = Merge_Sort(p_array_izquierdo);

            // Se ordenan recursivamente los elementos que contiene el array derecho.
            p_array_derecho = Merge_Sort(p_array_derecho);

            // Se fusionan los elementos del array izquierdo y el array derecho.
            //   [ Array Izquierdo ]                     [ Array Derecho ]
            //            |                                     |
            //            ----------[ Array Resultado ]----------
            //
            p_array_resultado = Merge(p_array_izquierdo, p_array_derecho);
            
            return p_array_resultado;

        }//Fin de: public void Merge_Sort()

        /// <summary>
        /// Funcion para crear un Array.
        /// </summary>
        /// <returns> El array creado.</returns>
        public int[] CrearArray() {

            int [] p_array= new int[20];

            int tamaño_array;

            Console.WriteLine("Creando el array a organizar...");
            Console.Write("Ingrese el tamaño del array: ");
            
            //Se solicita el ingreso de un valor numérico para el tamaño del array
            //Rodeado por un try - catch para asegurarse que no se acepten otros valores de entrada 
            try
            {
                tamaño_array = int.Parse( Console.ReadLine() );

                while (tamaño_array < 2) {

                    Console.WriteLine("¿Por que ordenarias un array de un solo elemento o menos?");
                    Console.WriteLine("¡Ingresa un valor valido!");
                    tamaño_array = int.Parse(Console.ReadLine());
                }

                p_array = new int[tamaño_array];

            }
            catch (Exception)
            {
                Console.WriteLine("Ingrese un valor valido. Solo se acepta un valor numérico entero.\n");
                Console.WriteLine("Presione cualquier tecla para continuar...");
                Console.ReadKey();
                Console.Clear();
                CrearArray();
            }
            
            Console.WriteLine("Ingrese los elementos dentro del array.");

            //Se solicita el ingreso de los elementos que contendra el array 
            //Rodeado por un try - catch para asegurarse que no se acepten otros valores de entrada 
            try
            {
                for (int i = 0; i < p_array.Length; i++)
                {
                    Console.Write("Posicion {0}: ", i );
                    p_array[i] = int.Parse(Console.ReadLine());
                    Console.WriteLine("El elemento en la posición {0} es el numero {1}",i , p_array[i] );
                }
            }
            catch (Exception)
            {
                Console.WriteLine("El array solo puede contener valores numericos.\n");
                Console.WriteLine("Presione cualquier tecla para continuar...");
                Console.ReadKey();
                Console.Clear();
                CrearArray();
            }
            
            return p_array;

        }//public int[] CrearArray() 


        /// <summary>
        /// Funcion para recorrer el array y mostrarlo por consola.
        /// </summary>
        /// <param name="p_array_entrada"> El Array a mostrar.</param>
        public void MostrarArray(int[] p_array_entrada)
        {

            // Por cada uno de los valores dentro del array de entrada
            Console.Write("- ");
            foreach (int numero in p_array_entrada)
            {
                // Mostrar por consola
                Console.Write(" {0} ", numero);
            }

            Console.WriteLine(" -");

        }// Final de: public void MostrarArray( int[] p_array_entrada )


        public void OrdenarConMergeSort()
        {

            // Mensaje de Bienvenida
            Console.ForegroundColor = ConsoleColor.Green;
            Console.WriteLine("------------------------------------------------------------");
            Console.WriteLine("Ejercicio Platzi - Mi solución de Merge Sort para C#.");
            Console.WriteLine("------------------------------------------------------------");

            //Crear el array
            int[] p_array_entrada = CrearArray();

            // Mostrar Array original
            Console.WriteLine("\n");
            Console.WriteLine("------------------------------------------------------------");
            Console.WriteLine("Array Original:");
            MostrarArray(p_array_entrada);
            Console.WriteLine("------------------------------------------------------------");

            // Mostrar Array Ordenado con Merge Sort
            Console.WriteLine("Array ordenado con Merge Sort:");
            
            MostrarArray( Merge_Sort(p_array_entrada) );

            Console.WriteLine("------------------------------------------------------------");
            Console.WriteLine("Finalizado - ¡Nunca pares de aprender! 8) ");
            Console.WriteLine("------------------------------------------------------------\n");

        }// Fin de: public void OrdenarConMergeSort()

        // Ejemplo para utilizar en el main
        // MergeSort ms = new MergeSort();
        // ms.OrdenarConMergeSort();

    }//class MergeSort```

Una pregunta este código me tira error de que la recursión no para. Alguien me ayuda?

#include <stdio.h>

int merge_sort(int a[])
{
    int i;
    int n = sizeof(a) / sizeof(a[0]);

    if(n < 2)
    {
        return a[n-1];
    }

    int mid = n/2;

    int left[mid];
    int right[n - mid];

    for(i = 0; i < mid; i++)
    {
        left[i] = a[i];
    }
    
    for(i; i < n; i++)
    {
        right[i - mid] = a[i];  
    }
    
    merge_sort(left);
    merge_sort(right);
    merge(left, right, a);

    return 0;
}

int merge(int l[], int r[], int a[])
{
    int i, j, k;
    int nl = sizeof(l) / sizeof(l[0]);
    int nr = sizeof(r) / sizeof(r[0]);

    while(i < nl && j < nr)
    {
        if(l[i] <= r[j])
        {
            a[k] = l[i];
            i ++;
        }
        else
        {
            a[k] = r[j];
            j ++;
        }
        k ++;
    }
}


int main()
{
    int ar[] = {1,2,7,6};
    merge_sort(ar);

    return 0;
}

MergeSort hecho en Python

def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r- m 
  
    #creamos vectores temporales
    L = [0] * (n1) 
    R = [0] * (n2) 
  
    #copiamos los datos en los vectores L y R
    for i in range(0 , n1): 
        L[i] = arr[l + i] 
  
    for j in range(0 , n2): 
        R[j] = arr[m + 1 + j] 
  
    #fusionar los nuevos vectores temporales
    i = 0     #inicializa el vector L
    j = 0     #inicializa el vector R
    k = l     #inicializa el merge
  
    while i < n1 and j < n2 : 
        if L[i] <= R[j]: 
            arr[k] = L[i] 
            i += 1
        else: 
            arr[k] = R[j] 
            j += 1
        k += 1
  
    #si sobra al algun elemento en L, copiarlo nuevamente
    while i < n1: 
        arr[k] = L[i] 
        i += 1
        k += 1
  
    #copiar algun elemento restante de R
    while j < n2: 
        arr[k] = R[j] 
        j += 1
        k += 1
  
#l es para el indice de la izquierda y r es para el indice de la derecha del vector que se desea ordenar
def mergeSort(arr,l,r): 
    if l < r:
      m = (l+(r-1))//2
  
      mergeSort(arr, l, m) 
      mergeSort(arr, m+1, r) 
      merge(arr, l, m, r) 
  
  
#vector con los numeros que deseamos ordenar
arr = [15, 20, -12, 0, 5, 6, 3, 1] 
n = len(arr) 
  
mergeSort(arr,0,n-1) 
print ("Vector ordenado") 
for i in range(n): 
    print ("%d" %arr[i]), 

Cómo es la resolución del stack en la función merge_sort? Se invoca a sí misma dos veces e invoca a otra función. Cuál ejecuta la recursividad primero? O se ejecutan en paralelo?

Aqui convertido a C# aplicando el codigo del mister.

Implementación en Java:

import java.util.*;

public class MergeSort {
	
	public static void main(String args[]) {
		
		Integer[] array = {3, 94, 86, 82, 90,
				10, 87, 36, 61, 8,
				17, 15, 22, 10, 23,
				78, 25, 2, 30, 45,
				98, 43, 98, 59, 53,
				57, 2, 64, 1, 41,
				32, 58, 19, 99, 60,
				74, 48, 80, 44, 25,
				68, 1, 89, 77, 60,
				25, 99, 30, 76, 32,
				57, 82, 52, 44, 72,
				87, 34, 87, 65, 30,
				54, 6, 31, 33, 44,
				44, 42, 82, 90, 17,
				9, 98, 28, 86, 69,
				3, 17, 8, 45, 98,
				12, 47, 95, 43, 72,
				39, 41, 82, 74, 56,
				65, 79, 50, 26, 67,
				100, 24, 67, 38, 57};
		
		System.out.println("Longitud: "+array.length);
		
		array = margeSort(array);
		
		List arr = Arrays.asList(array);
		
		System.out.println("Longitud: "+array.length);
		
		System.out.println("Arreglo ordenado: "+arr);
	}
	
	private static Integer[] margeSort(Integer [] array) {
		int length = array.length;
		
		if(length > 1) {
			int middle = length / 2;
			Integer[] arrayLeft = new Integer[middle];
			Integer[] arrayRight = new Integer[length - middle];
			
			arrayLeft = Arrays.copyOfRange(array, 0, middle);
			arrayRight = Arrays.copyOfRange(array, middle, length);
			
			arrayLeft = margeSort(arrayLeft);
			arrayRight = margeSort(arrayRight);
			return merge(arrayLeft, arrayRight);
		}
		
		return array;
	}
	
	private static Integer[] merge(Integer[] arrayLeft, Integer[] arrayRight) {
		int length = arrayLeft.length + arrayRight.length;
		int middle = arrayLeft.length;
		int index = 0;
		int less = 0;
		Integer[] arrayResult = new Integer[length];
		
		if(arrayLeft[arrayLeft.length-1] > arrayRight[0]) {
			System.arraycopy(arrayLeft, 0, arrayResult, 0, middle);
			System.arraycopy(arrayRight, 0, arrayResult, middle, arrayRight.length);
			return arrayResult;
		}
		
		while(arrayLeft.length > 0 && arrayRight.length > 0) {
			if(arrayLeft[0] >= arrayRight[0]) {
				less = arrayLeft[0];
				arrayLeft = Arrays.copyOfRange(arrayLeft, 1, arrayLeft.length);
			}else {
				less = arrayRight[0];
				arrayRight = Arrays.copyOfRange(arrayRight, 1, arrayRight.length);
			}
			arrayResult[index] = less;
			index++;
		}
		
		if(arrayLeft.length > 0) {
			System.arraycopy(arrayLeft, 0, arrayResult, index, arrayLeft.length);
		}else if(arrayRight.length > 0) {
			System.arraycopy(arrayRight, 0, arrayResult, index, arrayRight.length);
		}
		
		return arrayResult;
	}
	
}

//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;
}

Estuve analizando el codigo, y lo copie tal cual esta y no imprime Bien XD adicional si le agrego numeros negativos se rompe, seguire intentando ver que hace el algoritmo.

ceci n’est pas une clase…

Hola compañeros. ¿Alguno de ustedes conoce un libro sobre algoritmos para complementar el curso y que quiere recomendarme?

No manches me tarde como una hora y media tratando de ver porque funcionaba el algortimo que pasa tras cada linea de codigo, ahora medianamente lo comprendo solo quiero agregar esto:

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++];// en esta parte es como si tuvieramos algo así
				  						//arr[k] = arr1[i];
										  // i = i + 1;
					
    else
      arr[k]=arr2[j++]; // en esta parte es como si tuvieramos algo así
				  						//arr[k] = arr2[j];
										  // j = j + 1;
  }
  
  return 0;
}

Funciona así por la manera en que entiende c este operador “+ +”.
si se pone antes es decir ++i le va a sumar una unidad al valor i antes de la expresión y si se pone *i++ lo va hacer despues de la expresión en este caso despues de la asignación

Implementación en python

<code>
vectorIn = []
def fillList(n)
    for i in n:
        vectorIn[i] = input("Introduce una número ")
        
def mergeSort(vectorIn): 
    if len(vectorIn) >1: 
        half = len(vectorIn)//2 
        list1 = vectorIn[:half]
        list2 = vectorIn[half:] 
        mergeSort(list1)
        mergeSort(list2) 
        i = 0
        j = 0
        k = 0 
        while i < len(list1) and j < len(list2): 
            if list1[i] < list2[j]: 
                vectorIn[k] = list1[i] 
                i+=1
            else: 
                vectorIn[k] = list2[j] 
                j+=1
            k+=1     
        while i < len(list1): 
            vectorIn[k] = list1[i] 
            i+=1
            k+=1          
        while j < len(list2): 
            vectorIn[k] = list2[j] 
            j+=1
            k+=1
  
def result(vectorIn): 
    for i in range(len(vectorIn)):         
        print(vectorIn[i],end=" ") 
    print() 
  
n = input("Introduce el tamañp de la lista")
fillList(n)
mergeSort(vectorIn) 
result(vectorIn) 

Estuve estudiando a fondo el código que dejó Ricardo Celis (“el profesor”) de arriba, y me dí cuenta que en algunos puntos ‘high’ llega a valer 0, y al pasar a “merge_sort(arr,mid+1,high);” como mágicamente vale 1 de nuevo, ¿Alguien sabe por qué sucede eso? Si lo quieren comprobar solo agregan un “printf(”%d\n", high");" antes del int mid; y otro en este lugar:

    merge_sort(arr,low,mid);
    printf("%d\n", high);
    merge_sort(arr,mid+1,high);

Implementación en C con la posibilidad de ingresar los numeros mediante standard input.

Creo que es un tema que merece la pena ser bien explicado y ejemplificado. Esta clase deja mucho que desear…

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

int merge (int * vector, int min, int mid, int max)
{
    // Se deberan crear dos vectores de comparacion
    // El tamanio de cada vector estara dado por los numeros n1 y n2
    int n1 = mid - min + 1;
    int n2 = max - mid;

    int vectorComparacion1[n1]; 
    int vectorComparacion2[n2];

    for (int i = 0; i < n1; i++)
    {
        vectorComparacion1[i] = vector[min+i];
    }
    for (int i = 0; i < n2; i++)
    {
        vectorComparacion2[i] = vector[mid+1+i];
    }

    //Comparacion y ordenamiento
    int i = 0;
    int j = 0;

    int goOn = 1;

    for (int k = min; k <= max; k++)
    {
        // Cuando se llega la final del vector de comparacion 1, ingresare los valores
        // restantes del vector de comparacion 2 (ya que estan ordenados)
        if (i == n1)
        {
            goOn = 0;
            vector[k] = vectorComparacion2[j];
            j++;
        }
        // Cuando se llega la final del vector de comparacion 2, ingresare los valores
        // restantes del vector de comparacion 1 (ya que estan ordenados)
        else if (j == n2)
        {
            goOn = 0;
            vector[k] = vectorComparacion1[i];
            i++;
        }

        // Si goOn no se ha seteado a 1, se entiende que no se llego al final de ningun vector
        // de comparacion.
        if (goOn)
        {
            if (vectorComparacion1[i] <= vectorComparacion2[j])
            {
                    vector[k] = vectorComparacion1[i];
                    i++;
            }
            else
            {
                    vector[k] = vectorComparacion2[j];
                    j++;
            }
        }        
    }
}

int mergeSort(int * vector, int min, int max)
{
    if (min == max)
    {
        return 0;
    }
    else
    {
        int mid = (min + max)/2;
        mergeSort(vector, min, mid);
        mergeSort(vector, mid+1, max);
        merge(vector, min, mid, max);
    }
}        

void printVector(int * vector, int vectorSize)
{
    for (int i = 0; i < vectorSize; i++)
    {
        printf("%d ", vector[i]);
    }
    printf("\n");
}

int main (int argc, const char * argv[])
{
	char line[255];
    int vectorSize = 0;

	FILE * filePointer = fopen(argv[1], "r");

    while (fgets(line, sizeof(line), filePointer) != NULL)
    {
        vectorSize++;
    }

    int vector[vectorSize];
    int i = 0;

    filePointer = fopen(argv[1], "r");
    printf("El tamanio del vector es: %d\nY su orden inicial es: ", vectorSize);
	while (fgets(line, sizeof(line), filePointer) != NULL)
	{
		vector[i] = atoi(line);
        printf("%d ", vector[i]);
        i++;
	}
    printf("\n");
	fclose(filePointer);

    mergeSort(vector, 0, vectorSize-1);

    printf("Vector ordenado: ");
    printVector(vector, vectorSize);
	
	return 0;
}```

en java

public class OrdenamientoRecursividad {

    public void merge_sort (int [] values, int low, int high){
        int mid ;
        if(low < high){
            mid = (low + high)/2;
            merge_sort(values, low, mid);
            merge_sort(values, mid +1, high);
            merge(values, low, mid, high);
        }


    }

    public void merge (int []values, int l, int m, int h ){
        int n1, n2,  i, j;

        n1 = m-l+1;
        n2 = h-m;


        int [] values1 = new int[n1];
        int [] values2 = new int[n2];



        for (i = 0; i <n1 ; i++)
            values1[i] = values[l + i];

        for (j = 0; j <n2 ; j++)
            values2[j] = values[m+1+j];

            i =0;
            j=0;

        int k = l;
        while (i < n1 && j< n2){
            if(values1[i]<= values2[j] ){
                values[k] = values1[i];
                i++;
            }else {
                values[k]= values2[j];
                j++;
            }
            k++;
        }

        while (i < n1){
            values[k]= values1[i];
            i++;
            k++;
        }

        while (j < n2){
            values[k]= values2[j];
            j++;
            k++;
        }

    }

    public void print (int []values){
        for (int z = 0; z <values.length ; z++) {
            System.out.println(values[z]);
        }
    }
}

//////////////////////
public class Main {

    public static void main(String[] args) {
            int [] values = {12,11,13,5,6,7};
            OrdenamientoRecursividad orden = new OrdenamientoRecursividad();
            orden.print(values);
            orden.merge_sort(values, 0, values.length-1);
            System.out.println("ordenado");
            orden.print(values);
    }


}

No me deja subir la imagen. Ni en esta ni en la otra clase. Tampoco con la Lap ni con la Desktop.

Genial!!

Fue un tanto complicado de entender y de hecho en una clase pasada me pasé un par de días intentando implementar este mergeSort, pero no logré terminarlo. Para comprender los números que se evaluaban agregué la siguiente línea después de las dos llamadas recursivas de merge_sort():

merge_sort(arr,low,mid);
merge_sort(arr,mid+1,high);
printf("Low [ %d ], middle [ %d ], high [ %d ]\n",arr[low], arr[mid], arr[high]);

#include<iostream>
using namespace std;

int arr[]={12,-45,-60,23,56,-90,90,89,45,23};

int merge(int arr[],int l, int m, int h)
{
  int arr1[5],arr2[5];
  int n1=m-l+1,n2=h-m,i,j;
  //Divide al arreglo en sup arreglos
  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;
  arr2[j]=9999;

  i=j=0;
 //Se ordena el arreglo
  for(int k=l;k<=h;k++)
  {
     if(arr1[i]<=arr2[j])
       arr[k]=arr1[i++];
     else
       arr[k]=arr2[j++];
  }

  return 0;
}

int mergeSort(int arr[], int low, int high)
{
   int mid;
   if(low<high)
   {
     mid=(low+high)/2;
     //Divide
     mergeSort(arr,low,mid);
     mergeSort(arr,mid+1,high);
     //Merge
     merge(arr,low,mid,high);
   }
}


int main()
{
   mergeSort(arr,0,10-1);
   for(int i=0;i<10;i++)
       cout<<arr[i]<<" ";


return 0;
}

Mi aporte en c++

Para una mejor visualización de los resultados propongo mejorar el código reemplazando las línea en la función main

printf("Sorted array:");  // print sorted array
  for(i=0;i<n;i++)
    printf("%d",arr[i]);

Por :

printf("Sorted array: {");  // print sorted array
  for(i=0;i<n;i++)
    printf(" %d",arr[i]);
  printf("}\n");

Básicamente dejo un espacio entre valores y abro y cierro corchetes

En golang, me complique un poco haciendo el código con la parte de salirme del indice de arr1 y arr2 pero lo solucione con un if

package main

import "fmt"

var arr = []int{9, 5, 3, 7, 20, 13, 2, -1, -5, 6, 7}

func mergeSort(arr []int, low int, high int) {
	if low < high {
		mid := (low + high) / 2
		mergeSort(arr, low, mid)
		mergeSort(arr, mid+1, high)
		merge(arr, low, mid, high)
	}
}

func merge(arr []int, low int, mid int, high int) {
	var arr1, arr2 []int
	for i := low; i < mid+1; i++ {
		arr1 = append(arr1, arr[i])
	}
	for i := mid + 1; i <= high; i++ {
		arr2 = append(arr2, arr[i])
	}
	lowAux, highAux := 0, 0
	for k := low; k <= high; k++ {
		if lowAux < len(arr1) && highAux < len(arr2) {
			if arr1[lowAux] <= arr2[highAux] {
				arr[k] = arr1[lowAux]
				lowAux++
			} else {
				arr[k] = arr2[highAux]
				highAux++
			}
		} else if lowAux == len(arr1) {
			arr[k] = arr2[highAux]
			highAux++
		} else {
			arr[k] = arr1[lowAux]
			lowAux++
		}
	}
}

func main() {
	n := len(arr)
	fmt.Printf("largo del array: %d\n", n)
	mergeSort(arr, 0, n-1)
	fmt.Printf("Array ordenado: %v", arr)
}

Comparto mi adaptacion a Js con algunas anotaciones que me parecieron necesarias:

let merge = (left, right) =>{   // ORDENA
    let arr = [];
    //array va a ir guardando valores ordenados

    while (left.length && right.length) {
        //proceso se repite hasta que alguno de los array no tenga datos

        if (left[0] < right[0]) {
        // Comparamos la primer posicion de cada array  --> al menor lo mandamos al array ordenador

        arr.push(left.shift());
    } else {
        arr.push(right.shift());
    }
    
    // .shift --> devuelve el valor [0] de un array y lo elimina del set de datos 
    }
    return arr.concat(left.concat(right));
}


let mergeSort = (arr) => {  // DIVIDE
    if (arr.length < 2) {
        return arr;
    }

    const middle = Math.floor(arr.length / 2);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}
  
let array = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8];

arrayNuevo = mergeSort(array);
console.log(arrayNuevo)

Da que desear esta clase

se podria hacer este algoritmo margeSort sin recursividad, unicamente con bucles?

Algo comprensible

Hice una pequeña modificación a la función merge, esta se me hizo mas fácil de entender.

int merge(int arr[],int l,int m,int h)
{
  int temp[h-l+1];
  int i=l,j=m+1, k=0;
  while (i<=m && j<=h)
  {
      if (arr[i]<=arr[j]) {
          temp[k]=arr[i];
          k++; i++;
      }
      else {
          temp[k]=arr[j];
          k++; j++;
      }
  }
  while (i<=m)
  {
      temp[k]=arr[i];
      k++; i++;
  }
  while (j<=h)
  {
      temp[k]=arr[j];
      k++; j++;
  }
  for (i = l; i <=h ; i++)
  {
      arr[i]=temp[i-l];
  }                             
  
  return 0;
}

Hola amigos,

Si pueden ayudarme, al tratar de replicar el ejercicio me resulta en este error:

Buenos días Amig@s,

La función merge_sort(), divide el arreglo y se van generando diferentes valores de mid, low y high, pero la función merge(), utiliza esos valores mid, low, high, cuales de esos valores utiliza? los mid,low, high, del arreglo antes de ser dividido?

Mil gracias