Recently, AlphaDev has shown significant advances in the synthesis of branchless sorting kernels for arrays of lengths $3$ to $5$. In this paper, we propose an enumerative search technique based on A* search and present novel optimality-preserving heuristics and non-optimality-preserving cuts for sorting kernel synthesis. Our algorithm outperforms AlphaDev in synthesis time by two orders of magnitude ran on a standard notebook instead of a TPU cluster. Because our algorithm can explore the solution space, we are able to enumerate all correct sorting kernels for length $3$ and simply select the best-performing one. For larger array lengths, we intelligently sample the solution space and find a sorting kernel that outperforms the state-of-the-art. Furthermore, we establish a new tight lower bound for the shortest sorting kernel for length $4$. Finally, we provide a comprehensive comparison against several other existing synthesis techniques and show that none of them is able to synthesize sorting kernels for arrays longer than $3$.