Dada la lista ordenada de vertices de un poligono, ordenar las abcisas de los mismos. Idem para dos poligonos.

El problema con el algoritmo presentado es que, visualmente, resulta bastante evidente cuales son las rectas verticales consecutivas que determinan las regiones de la figura, pero esto no es tan evidente si pensamos en que nos dan, simplemente, dos listas ordenadas (los vertices de cada poligono) de miles de puntos en el plano y queremos saber cmo se intercalan entre si los distintos puntos para formar una unica lista ordenada por las abscisas de los puntos.

En primer lugar deberiamos empezar ordenando por las abscisas los vertices de cada uno de los dos poligonos. Es facil obtener, en tiempo lineal en el numero de elementos (es decir, N) el menor o mayor de una lista.

Asi determinariamos, por ejemplo, que los vertices 1 y 5 son los extremos de los vertices del poligono P, respecto de la ordenacin por abscisas.

Ahora, por la convexidad del poligono, resulta que tenemos dos listas ordenadas que empiezan en 1 y terminan en 5, [1, 2, 3, 4, 5] y [1, 5], respectivamente, obtenidas recorriendo en la direccin del reloj y en la direccin contraria los vertices de P entre el vertice 1 y el vertice 5. A partir de estas dos listas debemos formar una sla lista que ordene las abscisas de los vertices de P. En este caso es trivial intercalar ambas listas para obtener la lista ordenada completa, pero en cualquier caso se procederia del mismo modo que en el problema, mas general, de ordenar las abscisas de todos los vertices de dos poligonos, que vamos a mostrar a continuacin.

Consideremos, pues, como datos, los vertices de P y de Q ordenados por abscisas, formando dos listas: [1, 2, 3, 4, 5] y [6, 7, 8, 9] ÀCmo intercalar los vertices de una y otra lista para tener una unica lista ordenada? Comenzamos tratando de ubicar el 6 en la primera lista, por ejemplo. Comparamos el 6 con 1 y decidimos que tiene abscisa mas grande, y hacemos lo mismo con 2. Pero vemos que tiene abscisa menor que la del vertice 3. Asi que la lista intercalada empezara por la serie [1, 2, 6, 3, ...] y observamos que este trozo lo hemos obtenido con solo tantas operaciones como el puesto que ocupa el vertice 6 en la nueva lista. Seguimos con el vertice 7, y, como la lista [6, 7, 8, 9] ya viene ordenada, solo lo necesitamos comparar con los vertices siguientes a 6, en la lista de P, es decir 3 y 4, concluyendo que la lista va a continuar como [1, 2, 6, 3, 7,...]. Notese que hemos hecho, en total 3+2 comparaciones, tantas como el puesto que ocupa en la lista el ultimo vertice que hemos intercalado, el 7. Cogemos ahora el vertice 8, y vemos que es mayor que el vertice 4 y que el vertice 5, pero menor que 9. Asi la lista definitiva es [1, 2, 6, 3, 7, 4, 5, 8, 9] y nos ha costado 2+3+3=8 comparaciones, es decir, tantas como el puesto del ultimo vertice. En resumen, si las listas dadas son de menos de N numeros, la mezcla ordenada nos llevara, tambien, menos de N pasos.