A new algorithm for Jordan sorting: its average-case analysis Original Research Article

Given the intersection points of a planar Jordan curve with the x-axis in the order in which they occur along the curve, sort them into the order in which they occur along the x-axis. In this paper, the average-case analysis of a new simple algorithm that solves the above-mentioned problem is presented. A certain model of generating random Jordan sequences is introduced. The results of the analysis are summarised in the form of theorems that specify the conditions under which the algorithm runs in linear expected time. The results are verified experimentally by a computer simulation.