Divide y vencerás

def mergesort(a, desde, hasta):
    """Ordena a[desde:hasta] partiéndolo por la mitad, ordenando cada mitad y mezclándolas."""
    if hasta - desde <= 1:                # caso base: 0 o 1 elementos ya están ordenados
        return
    medio = (desde + hasta) // 2
    mergesort(a, desde, medio)            # vencer: cada mitad, recursivamente
    mergesort(a, medio, hasta)
    mezclar(a, desde, medio, hasta)       # combinar


def mezclar(a, desde, medio, hasta):
    """Mezcla dos tramos ordenados consecutivos en uno ordenado."""
    tmp = []
    i, j = desde, medio
    while i < medio and j < hasta:        # el menor de los dos
        if a[i] <= a[j]:
            tmp.append(a[i])
            i += 1
        else:
            tmp.append(a[j])
            j += 1
    tmp.extend(a[i:medio])                # lo que quede de la izquierda
    tmp.extend(a[j:hasta])                # o de la derecha
    a[desde:hasta] = tmp


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

/** Ordena a[desde..hasta) partiéndolo por la mitad, ordenando cada mitad y mezclándolas. */
function mergesort(a, desde, hasta) {
    if (hasta - desde <= 1) return;                // caso base: 0 o 1 elementos ya están ordenados
    const medio = Math.floor((desde + hasta) / 2);
    mergesort(a, desde, medio);                    // vencer: cada mitad, recursivamente
    mergesort(a, medio, hasta);
    mezclar(a, desde, medio, hasta);               // combinar
}

/** Mezcla dos tramos ordenados consecutivos en uno ordenado. */
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++]);  // el menor de los dos
    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("[" + a.join(", ") + "]");

using System;

class Program {
    // Ordena a[desde..hasta) partiéndolo por la mitad, ordenando cada mitad y mezclándolas.
    static void Mergesort(int[] a, int desde, int hasta) {
        if (hasta - desde <= 1) return;                 // caso base: 0 o 1 elementos ya están ordenados
        int medio = (desde + hasta) / 2;
        Mergesort(a, desde, medio);                     // vencer: cada mitad, recursivamente
        Mergesort(a, medio, hasta);
        Mezclar(a, desde, medio, hasta);                // combinar
    }

    // Mezcla dos tramos ordenados consecutivos en uno ordenado.
    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++];  // el menor de los dos
        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("[" + string.Join(", ", a) + "]");
    }
}

<?php
/** Ordena $a[$desde..$hasta) partiéndolo por la mitad, ordenando cada mitad y mezclándolas. */
function mergesort(array &$a, int $desde, int $hasta): void {
    if ($hasta - $desde <= 1) return;               // caso base: 0 o 1 elementos ya están ordenados
    $medio = intdiv($desde + $hasta, 2);
    mergesort($a, $desde, $medio);                  // vencer: cada mitad, recursivamente
    mergesort($a, $medio, $hasta);
    mezclar($a, $desde, $medio, $hasta);            // combinar
}

/** Mezcla dos tramos ordenados consecutivos en uno ordenado. */
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++];  // el menor de los dos
    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 "[" . implode(", ", $a) . "]\n";

def potencia(x, n):
    """x elevado a n con O(log n) multiplicaciones: x^n = (x^(n/2))², por x si n es impar."""
    if n == 0:                        # caso base
        return 1
    mitad = potencia(x, n // 2)       # un solo subproblema, de la mitad de tamaño
    r = mitad * mitad                 # combinar
    return r if n % 2 == 0 else r * x


# Python ya lo hace así por dentro: pow(x, n) y x ** n; pow(x, n, m) además con módulo

/** x elevado a n con O(log n) multiplicaciones: x^n = (x^(n/2))², por x si n es impar. */
function potencia(x, n) {
    if (n === 0) return 1n;                    // caso base
    const mitad = potencia(x, Math.floor(n / 2));  // un solo subproblema, de la mitad de tamaño
    const r = mitad * mitad;                   // combinar
    return n % 2 === 0 ? r : r * x;
}

// Con BigInt (1n, 2n…) los resultados grandes son exactos: potencia(2n, 100)

// x elevado a n con O(log n) multiplicaciones: x^n = (x^(n/2))², por x si n es impar.
static long Potencia(long x, int n) {
    if (n == 0) return 1;                  // caso base
    long mitad = Potencia(x, n / 2);       // un solo subproblema, de la mitad de tamaño
    long r = mitad * mitad;                // combinar
    return n % 2 == 0 ? r : r * x;
}

/** $x elevado a $n con O(log n) multiplicaciones: x^n = (x^(n/2))², por x si n es impar. */
function potencia(int $x, int $n): int {
    if ($n === 0) return 1;                  // caso base
    $mitad = potencia($x, intdiv($n, 2));    // un solo subproblema, de la mitad de tamaño
    $r = $mitad * $mitad;                    // combinar
    return $n % 2 === 0 ? $r : $r * $x;
}