Fuera de Orden (Platino)

Pensando en oportunidades profesionales a largo plazo más allá de la granja, la vaca Bessie ha comenzado a aprender algoritmos en varios sitios web de programación. Sus dos algoritmos favoritos son "bubble sort" y "quicksort", pero desafortunadamente, Bessie los confunde fácilmente y termina implementando un híbrido bastante extraño de ambos.

Llamemos punto de partición a la posición entre los elementos $i$ e i + 1 de un arreglo $A$ si el máximo de A_0, \ldots, A_i no es mayor que el mínimo de A_{i+1}, \ldots, A_{n-1}. Bessie recuerda que quicksort reorganiza el arreglo de modo que tenga un punto de partición y luego ordena recursivamente las dos partes A_0, \ldots, A_i y A_{i+1}, \ldots, A_{n-1}. Sin embargo, aunque ella nota correctamente que todos los puntos de partición de un arreglo pueden encontrarse en tiempo lineal, ¡ha olvidado cómo se supone que quicksort debe reorganizar el arreglo para crear rápidamente un punto de partición! En lo que podría resultar ser el peor error algorítmico en la historia de la ordenación, toma la desafortunada decisión de usar bubble sort para esta tarea.

Aquí hay un esbozo de la implementación de Bessie para ordenar un arreglo $A$. Primero, escribe una función simple que realiza una pasada de bubble sort:

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

El código recursivo de su función quick(ish) sort está estructurado de la siguiente manera:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A)
   divide A at all partition points; recursively quickish_sort each piece
}

Bessie tiene curiosidad por saber qué tan rápido se ejecutará su código. Para simplificar, asume que cada iteración del bucle principal toma tiempo lineal, por lo que incrementa la variable global work\_counter dentro del bucle en consecuencia para llevar la cuenta del trabajo total realizado por el algoritmo.

Dado el arreglo de entrada, predice el valor final de work\_counter después de que el arreglo sea ordenado por quickish\_sort.