Abstract
Bayesian Optimization (BO) algorithm is a standard tool for black-boxoptimization problems. The current state-of-the-art BO approach for permutationspaces relies on the Mallows kernel-an $\Omega(n^2)$ representation thatexplicitly enumerates every pairwise comparison. Inspired by the closerelationship between the Mallows kernel and pairwise comparison, we propose anovel framework for generating kernel functions on permutation space based onsorting algorithms. Within this framework, the Mallows kernel can be viewed asa special instance derived from bubble sort. Further, we introduce the\textbf{Merge Kernel} constructed from merge sort, which replaces the quadraticcomplexity with $\Theta(n\log n)$ to achieve the lowest possible complexity.The resulting feature vector is significantly shorter, can be computed inlinearithmic time, yet still efficiently captures meaningful permutationdistances. To boost robustness and right-invariance without sacrificingcompactness, we further incorporate three lightweight, task-agnosticdescriptors: (1) a shift histogram, which aggregates absolute elementdisplacements and supplies a global misplacement signal; (2) a split-pair line,which encodes selected long-range comparisons by aligning elements across thetwo halves of the whole permutation; and (3) sliding-window motifs, whichsummarize local order patterns that influence near-neighbor objectives. Ourempirical evaluation demonstrates that the proposed kernel consistentlyoutperforms the state-of-the-art Mallows kernel across various permutationoptimization benchmarks. Results confirm that the Merge Kernel provides a morecompact yet more effective solution for Bayesian optimization in permutationspace.