Mergesort (ordenación por mezcla)

def mergesort(a, desde, hasta):
    """Ordena a[desde:hasta] y escribe cada mezcla que hace."""
    if hasta - desde <= 1:                      # 0 o 1 elementos: ya está ordenado
        return
    medio = (desde + hasta) // 2
    mergesort(a, desde, medio)                  # ordena la mitad izquierda
    mergesort(a, medio, hasta)                  # y la derecha
    izq, der = a[desde:medio], a[medio:hasta]
    mezclar(a, desde, medio, hasta)
    print(f"mezclar {izq} y {der} → {a[desde:hasta]}")


def mezclar(a, desde, medio, hasta):
    """Mezcla a[desde:medio] y a[medio:hasta], ya ordenados, en a[desde:hasta]."""
    tmp = []
    i, j = desde, medio
    while i < medio and j < hasta:
        if a[i] <= a[j]:                        # <= : estable
            tmp.append(a[i])
            i += 1
        else:
            tmp.append(a[j])
            j += 1
    tmp += a[i:medio] + a[j:hasta]              # lo que quede de una de las dos
    a[desde:hasta] = tmp


a = [38, 27, 43, 3, 9, 82, 10]
mergesort(a, 0, len(a))
print("Resultado:", a)

const texto = (a) => "[" + a.join(", ") + "]";

/** Ordena a[desde..hasta) y escribe cada mezcla que hace. */
function mergesort(a, desde, hasta) {
    if (hasta - desde <= 1) return;                 // 0 o 1 elementos: ya está ordenado
    const medio = Math.floor((desde + hasta) / 2);
    mergesort(a, desde, medio);                     // ordena la mitad izquierda
    mergesort(a, medio, hasta);                     // y la derecha
    const izq = texto(a.slice(desde, medio));
    const der = texto(a.slice(medio, hasta));
    mezclar(a, desde, medio, hasta);
    console.log(`mezclar ${izq} y ${der} → ${texto(a.slice(desde, hasta))}`);
}

/** Mezcla a[desde..medio) y a[medio..hasta), ya ordenados, en a[desde..hasta). */
function mezclar(a, desde, medio, hasta) {
    const tmp = [];
    let i = desde, j = medio;
    while (i < medio && j < hasta) tmp.push(a[i] <= a[j] ? a[i++] : a[j++]);   // <= : estable
    while (i < medio) tmp.push(a[i++]);             // lo que quede de la izquierda
    while (j < hasta) tmp.push(a[j++]);             // o de la derecha
    a.splice(desde, tmp.length, ...tmp);
}

const a = [38, 27, 43, 3, 9, 82, 10];
mergesort(a, 0, a.length);
console.log("Resultado: " + texto(a));

using System;

class Program {
    static string Texto(int[] a, int desde, int hasta) => "[" + string.Join(", ", a[desde..hasta]) + "]";

    // Ordena a[desde..hasta) y escribe cada mezcla que hace.
    static void Mergesort(int[] a, int desde, int hasta) {
        if (hasta - desde <= 1) return;                 // 0 o 1 elementos: ya está ordenado
        int medio = (desde + hasta) / 2;
        Mergesort(a, desde, medio);                     // ordena la mitad izquierda
        Mergesort(a, medio, hasta);                     // y la derecha
        string izq = Texto(a, desde, medio), der = Texto(a, medio, hasta);
        Mezclar(a, desde, medio, hasta);
        Console.WriteLine(
quot;mezclar {izq} y {der} → {Texto(a, desde, hasta)}");
    }

    // Mezcla a[desde..medio) y a[medio..hasta), ya ordenados, en a[desde..hasta).
    static void Mezclar(int[] a, int desde, int medio, int hasta) {
        int[] tmp = new int[hasta - desde];
        int i = desde, j = medio, k = 0;
        while (i < medio && j < hasta) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];   // <= : estable
        while (i < medio) tmp[k++] = a[i++];            // lo que quede de la izquierda
        while (j < hasta) tmp[k++] = a[j++];            // o de la derecha
        Array.Copy(tmp, 0, a, desde, tmp.Length);
    }

    static void Main() {
        int[] a = { 38, 27, 43, 3, 9, 82, 10 };
        Mergesort(a, 0, a.Length);
        Console.WriteLine("Resultado: " + Texto(a, 0, a.Length));
    }
}

<?php
function texto(array $a): string { return "[" . implode(", ", $a) . "]"; }

/** Ordena $a[$desde..$hasta) y escribe cada mezcla que hace. */
function mergesort(array &$a, int $desde, int $hasta): void {
    if ($hasta - $desde <= 1) return;               // 0 o 1 elementos: ya está ordenado
    $medio = intdiv($desde + $hasta, 2);
    mergesort($a, $desde, $medio);                  // ordena la mitad izquierda
    mergesort($a, $medio, $hasta);                  // y la derecha
    $izq = texto(array_slice($a, $desde, $medio - $desde));
    $der = texto(array_slice($a, $medio, $hasta - $medio));
    mezclar($a, $desde, $medio, $hasta);
    echo "mezclar $izq y $der → " . texto(array_slice($a, $desde, $hasta - $desde)) . "\n";
}

/** Mezcla $a[$desde..$medio) y $a[$medio..$hasta), ya ordenados, en $a[$desde..$hasta). */
function mezclar(array &$a, int $desde, int $medio, int $hasta): void {
    $tmp = [];
    $i = $desde;
    $j = $medio;
    while ($i < $medio && $j < $hasta) $tmp[] = $a[$i] <= $a[$j] ? $a[$i++] : $a[$j++];   // <= : estable
    while ($i < $medio) $tmp[] = $a[$i++];          // lo que quede de la izquierda
    while ($j < $hasta) $tmp[] = $a[$j++];          // o de la derecha
    array_splice($a, $desde, count($tmp), $tmp);
}

$a = [38, 27, 43, 3, 9, 82, 10];
mergesort($a, 0, count($a));
echo "Resultado: " . texto($a) . "\n";

# sorted() y list.sort() usan TimSort, un mergesort mejorado: son estables.
alumnos = cargar_alumnos()
alumnos.sort(key=lambda a: a.nombre)      # primero por nombre…
alumnos.sort(key=lambda a: a.curso)       # …y luego por curso: dentro de cada curso
                                          # siguen ordenados por nombre

// Array.prototype.sort es estable desde ES2019 (V8 usa TimSort).
const alumnos = cargarAlumnos();
alumnos.sort((a, b) => a.nombre.localeCompare(b.nombre));   // primero por nombre…
alumnos.sort((a, b) => a.curso - b.curso);                   // …y luego por curso: dentro de cada
                                                             // curso siguen ordenados por nombre

// Ojo: List<T>.Sort NO es estable (usa introsort). OrderBy de LINQ sí lo es.
List<Alumno> alumnos = CargarAlumnos();
var ordenados = alumnos.OrderBy(a => a.Nombre)      // primero por nombre…
                       .OrderBy(a => a.Curso)        // …y luego por curso (estable)
                       .ToList();
// Lo habitual: alumnos.OrderBy(a => a.Curso).ThenBy(a => a.Nombre)

// Desde PHP 8.0, sort, usort y compañía son estables.
$alumnos = cargarAlumnos();
usort($alumnos, fn($a, $b) => strcmp($a->nombre, $b->nombre));   // primero por nombre…
usort($alumnos, fn($a, $b) => $a->curso <=> $b->curso);          // …y luego por curso: dentro de cada
                                                                 // curso siguen ordenados por nombre