#quickselect

It is simple. Get the list and sort all items Theta(N*log2(N)) and take k-th item.  Another way is to take incomplete quicksort and sort well only items <= k-th item.

The good explination is in this example and here.

Complexity

Work = n + n/2 + n/4 + …

To sum it all up, we can use the similarity rule:

Work/2 = n/2 + n/4 + n/8 + …

Hence:

Work – (Work/2) = n Work/2 = n Work = 2n Work = O(n)

public static class ArrayExtensions { public static T GetNthElement<T>(this T[] source, int nth) where T: IComparable<T> { if (source == null) throw new ArgumentNullException(); if (source.Count() == 0) throw new ArgumentOutOfRangeException(); var count = source.Count(); var from = 0; var to = count - 1; while(from < to) { var left = from; var right = to; int pivot = (left + right) / 2; var pivotValue = source[pivot]; while (left < right) { if(source[left].CompareTo(pivotValue) >= 0) { source.Swap(left, right); right--; } else { left++; } } if (source[left].CompareTo(pivotValue) > 0) left--; if (nth <= left) { to = left; } else { from = left + 1; } } return source[nth]; } private static void Swap<T>(this T[] array,int index1, int index2) { if (index1 == index2) return; var temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } }

[TestMethod] public void Find3rdLowerElement3() { var l = new int[] { 2, 1, 51, 52, 56, 35, 20 }; var x = l.GetNthElement(6); Assert.AreEqual(x, 56); x = l.GetNthElement(0); Assert.AreEqual(x, 1); x = l.GetNthElement(1); Assert.AreEqual(x, 2); }