Algoritmo para ordenar enteros

Una de las tareas más frecuentes cuando trabajas con datos es «ordenar» una serie o varias de datos. Así que como primer reto vas a intentar programar tu propia función para ordenar en este caso una serie de números enteros. Seguramente nunca más intentarás diseñar tu propio algoritmo para ordenar datos, encontrarás múltiples funciones en las librerías de Python que uses capaces de resolver esta tarea. Pero intentarlo tu desde cero te hará comprender el valor y el esfuerzo que hay detrás de herramientas tan comunes usadas de manera tan «alegre».

Tarea

Haz una función de Python llamada sort con un único argumento de entrada llamado numbers. La función deberá regresar la lista de números enteros que recibió como entrada (numbers) en orden de menor a mayor. Debes de tener en cuenta las siguientes condiciones:

• la lista contendrá \(10^7\) números enteros positivos en el rango \([0, 10^8)\).

• no tienes límite de recursos (memoria, número de cpus, etc.) a usar para conseguir que tu algoritmo sea eficiente.

• el algoritmo lo debes implementar haciendo uso de la sintaxis básica de Python -NO vale hacer uso de funciones ya programadas para ordenar que puedes encontrar en Numpy, Pandas, Scipy, etc-.

Esta es la lista de números que debes ordenar:

import numpy as np

rng = np.random.default_rng(333)
input_random_numbers = rng.integers(low=0, high=10**8, size=10**7)

print(input_random_numbers)

[30054056 91900182 41637891 ...  5150345 25101977 61734715]

Ahora es tu turno escribir tu función para ordenar esa lista:

def sort(numbers):
    
    #### Escribe aquí tu propuesta ####
    
    return sorted_numbers # 'sorted_numbers' o el nombre de la variable de salida que tu elijas

¿Ya tienes una propuesta que funciona? Genial! ¿Puedes calcular cuanto espacio en memoria ocupa el numpy.array input_random_numbers? O dicho de otra manera… ¿Cuanta memoria consumen \(10^7\) enteros?

### ES TU TURNO
### -----------------------------------
### Resuelve aquí la propuesta anterior
### en una o varias celdas

¿Y puedes calcular cuanto tiempo le cuesta a tu función ordenar los \(10^7\) enteros de input_random_numbers?

### ES TU TURNO
### -----------------------------------
### Resuelve aquí la propuesta anterior
### en una o varias celdas

Ahora si, prueba por ejemplo la función sort de la librería Numpy y calcula cuanto tiempo menos le cuesta a ella que a tu función:

%%time
sorted_numbers = np.sort(input_random_numbers)

CPU times: user 163 ms, sys: 12.2 ms, total: 175 ms
Wall time: 175 ms

¿Por qué crees que es más rápida?

Contesta aquí mismo