3.3.4. Ordenación por mezcla y ordenación rápida.
Se da cuando la matriz está ya ordenada. En este caso una partición tiene tamaño 0 y la otra n-1.
t(n) = t(n-1) + b·n + c ? O(n2)
Se puede comprobar que t(n) ? O(n·log n).
3.3.5. El problema de selección.
- Sea T[1..n] un array (no ordenado) de enteros, y sea s un entero entre 1 y n. El problema de selección consiste en encontrar el elemento que se encontraría en la posición s si el array estuviera ordenado.
- Si s = ?n/2?, entonces tenemos el problema de encontrar la mediana de T, es decir el valor que es mayor que la mitad de los elementos de T y menor que la otra mitad.
- Forma sencilla de resolver el problema de selección:
Ordenar T y devolver el valor T[s]. Esto requeriría O(n·log n)