This paper presents a Bayesian optimization (BO) algorithm for black-box optimization problems in permutation space. Existing state-of-the-art BO approaches rely on the Mallows kernel, which explicitly enumerates all pairwise comparisons and has Ω(n²) complexity. Inspired by the close relationship between the Mallows kernel and pairwise comparisons, this paper proposes a novel framework for generating kernel functions in permutation space based on sorting algorithms. Within this framework, the Mallows kernel can be viewed as a special instance derived from bubble sort. Furthermore, we present a Merge kernel constructed from merge sort, which replaces quadratic complexity with Θ(n log n) to achieve the lowest complexity. The resulting feature vector is significantly shorter and can be computed in linear-log time, while still efficiently capturing meaningful permutation distances. To improve robustness and right-hand side invariance while maintaining compactness, we additionally incorporate three lightweight, operation-independent descriptors: shift histogram, split-pair line, and sliding-window motifs. Experimental evaluations show that the proposed kernel consistently outperforms the state-of-the-art Mallows kernel on a variety of permutation optimization benchmarks. The results confirm that the Merge kernel provides a more compact and efficient solution to Bayesian optimization in permutation space.
