A simple and efficient algorithm for sorting the intersection points between a Jordan curve and a line

In this paper, we focus on the Jordan sorting problem: Given N intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve. The task is to sort these points into the order in which they occur along the x-axis. Contrary to general sorting whose solution (in the algebraic decision-tree model of computation) requires θ(N log N) time in the worst case, the Jordan sorting problem can be solved in θ(N) time. The linear worst-case time algorithms for Jordan sorting were proposed by Hoffman et al., and by Fung et al. Unfortunately, both these algorithms are rather complicated, which makes them difficult to use in practice. In this paper, we propose and analyse a simple algorithm for Jordan sorting. Although the worst-case time complexity of this algorithm is O(N log N), we show that the worst time is achieved only for special inputs. For most inputs, a better performance can be expected. We also show that for a certain class of inputs which may be of practical interest, the algorithm runs even in O(N) expected time. We believe that for many practical applications, the algorithm may be more advantageous than rather complicated worst-case time optimal algorithms. Our main result is the analysis of this otherwise rather straightforward algorithm