 # Purely Tail Recursive k-th Smallest Element

Finding the k-th smallest (or largest) element of an unordered array is a problem that's been approached by many programmers and computer scientists. There are many methods for solving this problem. To me, one of the more interesting implementations is a purely tail recursive implementation that uses the partition algorithm.

A purely tail recursive function or method is one in which there are no deferred operations. A deferred operation in this case, is one that must wait until a recursive call returns before it can complete. This article goes into this a little detail about the differences between "ordinary" and "pure" tail recursive methods.

Given a function that can swap two elements of an array and the partition function, it is possible to find the k-th smallest element of an array of distinct integers using the following purely tail recursive implementation (the accumulator parameters act in a fashion that is similar to a binary search):

private static int kthMin(int[] a, int left, int right, int k) {
int newPivot = partition(a, left, right, k - 1);
if (newPivot == k - 1) return a[k - 1];
if (newPivot < k - 1) left = newPivot + 1;
if (newPivot > k - 1) right = newPivot - 1;
return kthMin(a, left, right, k);
} // kthMin

If you have any questions, then please post them in the comments.