This problem can be solved using a straightforward comparison sort on the Cartesian product of the two given sets. When the sets have size, their product has size, and the time for a comparison sorting algorithm is. This is the bestupper bound known on the time for this problem. Whether sorting can be done in a more slowly-growing time bound is an open problem. suggest separately sorting and, and then constructing a two-dimensional matrix of the values of that is sorted both by rows and by columns before using this partially-sorted data to complete the sort of. Although this can reduce the number of comparisons needed by a constant factor, compared to naive comparison sorting, they show that any comparison sorting algorithm that can work for arbitrary matrices that are sorted by rows and columns still requires comparisons, so additional information about the set beyond this matrix ordering would be needed for any faster sorting algorithm.
Number of orderings
The numbers in the two input lists for the sorting problem can be interpreted as Cartesian coordinates of a point in the -dimensional space. If one partitions the space into cells, so the set has a fixed ordering within each cell, then the boundaries between these cells are hyperplanes defined by an equality of pairs. The number of hyperplanes that can be determined in this way is, and the number of cells that this number of hyperplanes can divide a space of dimension into is less than. Therefore, the set has at most different possible orderings.
Number of comparisons
The number of comparisons required to sort is certainly lower than for ordinary comparison sorting: Michael Fredman showed in 1976 that sorting can be done using only comparisons. More generally, he shows that any set of elements, whose sorted ordering has already been restricted to a family of orderings, can be sorted using comparisons, by a form of binary insertion sort. For the sorting problem,, and, so and Fredman's bound implies that only comparisons are needed. However, the time needed to decide which comparisons to perform may be significantly higher than the bound on the number of comparisons. If only comparisons between elements of are allowed, then there is also a matching lower bound of on the number of comparisons needed. The first actual algorithm that achieves both comparisons and total complexity was published sixteen years later. The algorithm first recursively sorts the two sets and, and uses the equivalence to infer the sorted orderings of and without additional comparisons. Then, it merges the two sets and and uses the merged order and the equivalence to infer the sorted order of without additional comparisons. The part of the algorithm that recursively sorts does so by splitting into two equal sublists and, recursively sorting and, inferring the ordering on as above, and merging the sorted results,, and together.
recounts a practical application in transit fare minimisation, an instance of the shortest path problem: given fares and for trips from departure A to some intermediate destination B and from B to final destination C, with only certain pairs of fares allowed to be combined, find the cheapest combined trip from A to C. Skiena's solution consists of sorting the pairs of fares as an instance of the sorting problem, and then testing the resulting pairs in this sorted order until finding one that is allowed. For this problem, one can use a priority queue of pairs, initialized to contain a single pair with the cheapest overall pair of fares. Then, when a pair is found to be disallowed, two more pairs formed by combining and with their successors in their respective sorted lists of single-hop fares can be added to the priority queue. In this way, each successive pair can be found in logarithmic time, and only the pairs up to the first allowable one need to be sorted. Several other problems in computational geometry have equivalent or harder complexity to sorting, including constructing Minkowski sums of staircase polygons, finding the crossing points of an arrangement of lines in sorted order by their -coordinates, listing pairs of points in sorted order by their distances, and testing whether one rectilinear polygon can be translated to fit within another.
