A kinetic sorted list is a kinetic data structure for maintaining a list of points under motion in sorted order.
This data structure maintains a list of the elements in sorted order, with the certificates enforcing the order between adjacent elements.
When a certificate fails, the concerned elements are swapped.
Then at most three certificates must be updated, the certificate of the swapped pair, and the two certificates involving the swapped elements and the elements of the sorted list which directly precede and follow the swapped pair.
The new set of certificates will be [A events total, assuming pseudo algebraic trajectories, where Thus, a maintenance-time versus query-time tradeoff can be made to tune to specific applications. In the generalized data structure, the points are partitioned arbitrarily into m subsets of size , and kinetic sorted lists are maintained on the subsets. Thus the total time required to maintain the data structure is Requests for the sorted list can then be answered in by merging the sorted sublists with mergesort.