Este problema es idéntico al problema 0xdd - Ordenar un arreglo pequeño pero con una entrada mucho más grande.
Uno de los problemas más famosos e importantes en programación consiste en ordenar los elementos de una arreglo.
Escribe un programa que lee N números y los ordena en orden no decreciente (es decir, de menor a mayor).
La idea de este problema es que implementes un algoritmo de sort desde cero. Para obtener 100 puntos, tu algoritmo debe tener complejidad de tiempo O(n log n).
Aunque en la práctica es raro implementar un algoritmo de sort desde cero (normalmente usas la implementación que ya existe en tu lenguaje), es fundamental conocerlos y entenderlos porque sus ideas pueden aplicarse a problemas más complejos.
Para este problema te recomiendo que implementes estos 3 algoritmos: quick sort, merge sort y heap sort.
La entrada contiene varias líneas:
N, el número de números que hay que ordenar.N enteros Ai para 0 ≤ i < N, los elementos a ordenar. Estos números están separados por espacios. Está garantizado que Ai satisface -109 ≤ Ai ≤ 109.La salida debe tener exactamente una línea con los mismos números de la entrada pero ordenados en orden no decreciente. Los números deben estar separados por espacios.
6
3 2 1 0 -1 0
-1 0 0 1 2 3
1 ≤ N ≤ 100,000. Este tamaño de N está diseñado para que algoritmos con complejidad O(n2) no corran a tiempo y sólo algoritmos con complejidad O(n log n) obtengan 100 puntos.