Binary Path Sort: A Sorting Algorithm to Assess the Preference Order of a Single Respondent

Sorting objects based on preference is integral to experimental research and applications across various disciplines, including psychology, marketing, and education. Under the transitivity assumption, it is not necessary to compare all objects directly to determine the preferred order. The field of computer science offers a rich literature on comparison-based sorting algorithms, presenting numerous strategies for the adaptive selection of pairwise comparisons. Typically, the focus is on minimizing resource utilization, such as computer memory. However, in many fields, particularly in psychology, comparisons are made by human respondents. Here, the key considerations are a low number of expected comparisons and a robust performance in worst-case scenarios. This study introduces Binary Path Sort (BPS), a novel and efficient sorting algorithm based on a priority queue. It will be demonstrated that BPS requires fewer element comparisons in the worst-case scenario compared to the currently best priority queue-based sorting algorithm. Moreover, BPS is equivalent in terms of the number of comparison required for best, average, and worst-case scenarios to the non-priority queue algorithm, Mergesort. A simulation study is presented to illustrate the avoidance of worst-case scenarios and which elements are compared. Finally, the study discusses the implications of these findings, particularly for forced-choice measurement applications.