Anytime Sorting Algorithms
Authors: Emma Caizergues, François Durand, Fabien Mathieu
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Simulations showcase the superior performance of both algorithms compared to existing methods. |
| Researcher Affiliation | Collaboration | 1Nokia Bell Labs, Massy, France 2CNRS Lamsade, Universit e Paris Dauphine PSL, Paris, France 3Swapcard Lab, Paris, France |
| Pseudocode | Yes | For the pseudocode, cf. Appendix A.3 in the extended paper. |
| Open Source Code | Yes | To compare the performance of ASort, multizip sort and Corsort with the classical sorting algorithms discussed in Section 2.1, we have developed an open-source Python package specifically designed for creating anytime sorting algorithms and evaluating their effectiveness [Caizergues et al., 2023] (cf. Appendix B in the extended paper). |
| Open Datasets | No | For each point, we generate 10,000 random lists and we record the number of comparisons required for a complete sort. The paper does not provide access information for a pre-existing, publicly available dataset. |
| Dataset Splits | No | For each point, we generate 10,000 random lists and we record the number of comparisons required for a complete sort. [...] For each algorithm, we sort 10,000 lists of size n = 1000. The paper generates random lists for evaluation but does not specify dataset splits like train/validation/test. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used for running the experiments (e.g., GPU/CPU models, memory specifications). |
| Software Dependencies | No | The paper mentions developing an 'open-source Python package' but does not specify any software versions for Python or other dependencies required for reproducibility. |
| Experiment Setup | Yes | For each point, we generate 10,000 random lists and we record the number of comparisons required for a complete sort. The curves for top-down merge, bottom-up merge, and multizip sort coincide as they represent different scheduling variations of mergesort. Similarly, the curves for ASort and quicksort are identical as they involve the same comparisons. We consider values of the list size n ranging from 8 to 2048. For each point, we generate 10,000 random lists and we record the number of comparisons required for a complete sort. The y-axis shows the relative deviation from the theoretical lower bound of log2(n!) = n log2(n) n/ ln(2) + log2(2πn)/2 + o(1) [Cormen et al., 2009]: a curve closer to 0 indicates closer proximity to the optimal performance. To give a comprehensive view of the results distribution, each algorithm s median is depicted by a dark curve, while the 2.5% to 97.5% quantiles form a 95% confidence interval represented by a light area. [...] For each algorithm, we sort 10,000 lists of size n = 1000. |