Optimality of 2-ary (binary) search trees

By law of Divide-and-Conquer, most algorithms that involve breaking problems down into a single subelement of itself uses binary tree as its data structure/abstract data type. Looking at the bread-and-butter algorithms like merge sort, binary search, a question popped up in my mind: why don’t we divide the problem up 3-way, or even 4-way? Wouldn’t that seem to be doing more at each level down the recursion and seem faster?

Note that the assumed topic is different from an optimal binary search tree, which is defined as a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum. The following evaluates the plausibility of using n-ary trees where n>2 to process divide-and-conquer problems.

Advertisements