Not an oracle related post. Life is stange, full of unexpectable scenerios. I think it wont be easy to make posts about oracle from now on. The below code is an algorithim comparision for finding th Nth element of a given list.

I found four algorithims for this problem. First is sorting the first N element and returning the last one. Sort algoritihm I used is no big deal, worst sorting ever. Second algorithm is very look like quicksort it is a divide&conquer, but the difference is we conquer just we need. Third algorithm is seconds in-place version. Third one had more code complexity but it is faster and absolutely less memory consuming than its sibling. Last one is Arrays.sort method, if I am not wrong it is a modified mergesort. Last one is absolutely tied to size, Nth element is not a factor in case we sort all the list.

First algorithm is tied to size of given list and the order of demanded element. Second algorithm creates each time new arrays. We can assume it creates log(n) arrays. Also each arrays size can be assumed is half of its ancestor. Because the algorithm is implemented in java, GC will be a factor in this case. GC is a very strong and mature part of jvm. It could be observed from scores, size is not a real factor for second algorithm. Indeed, a threashold exists for second algorithm. Exceeding this size threshold, makes this algorithm slower than the third one.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class SelectKth {
	private static int SIZE = 10000;
	private static Random r = new Random();

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println("algo\ttime\tth\tsize");

		for(SIZE = 10000; SIZE<100000; SIZE += 10000)
			for(int j=0; j<10;j++) {
				List list = new ArrayList(SIZE);
				populate(list);
				Integer[] conventionalNumbers = list.toArray(new Integer[SIZE]);
				Integer[] selectionNumbers = conventionalNumbers.clone();
				Integer[] selectionInPlaceNumbers = conventionalNumbers.clone();

				int i, th = r.nextInt(SIZE);

				long time = System.currentTimeMillis();
				i = conventional(conventionalNumbers, th);
				System.out.format("%d\t%d\t%d\t%d\n", 1, System.currentTimeMillis() - time,th,SIZE);

				time = System.currentTimeMillis();
				i = selection(selectionNumbers, th);
				System.out.format("%d\t%d\t%d\t%d\n", 2, System.currentTimeMillis() - time,th,SIZE);

				time = System.currentTimeMillis();
				i = selectionInPlace(selectionInPlaceNumbers, th, 0,
						selectionInPlaceNumbers.length - 1);
				System.out.format("%d\t%d\t%d\t%d\n", 3, System.currentTimeMillis() - time,th,SIZE);

				time = System.currentTimeMillis();
				Arrays.sort(selectionNumbers);
				System.out.format("%d\t%d\t%d\t%d\n", 4, System.currentTimeMillis() - time,th,SIZE);

			}
	}

	private static int selectionInPlace(Integer[] numbers, int th, int left,
			int right) {
		int pivot_idx = left;
		int pivot = numbers[left];
		int right_closure = right;

		if (right == left)
			return numbers[left];

		for (int i = left + 1; i <= right; i++) {
			if (numbers[i] = i)
					continue;
				else {
					swap(numbers, i, pivot_idx);
					pivot_idx = i;
				}
			else if (numbers[i] > pivot){
					for(; right_closure != pivot_idx && numbers[right_closure]>=pivot; right_closure--);
					if(right_closure == pivot_idx || i > right_closure)
						break;
					swap(numbers, i, right_closure--);
			}
		}

		if(right_closure != right) {
			for(; right_closure != pivot_idx && numbers[right_closure]>pivot; right_closure--);
			swap(numbers, right_closure, pivot_idx);
			pivot_idx = right_closure;
		}

		if (pivot_idx == th)
			return pivot;
		if (pivot_idx < th)
			return selectionInPlace(numbers, th, pivot_idx + 1, right);
		else
			return selectionInPlace(numbers, th, left, pivot_idx - 1);

	}

	private static Integer[] left_arr;
	private static Integer[] right_arr;

	private static int selection(Integer[] numbers, int th) {
		int pivot_idx = 0;

		if (numbers.length == 1)
			return numbers[0];
		else if (numbers.length == 2) {
			Arrays.sort(numbers);
			return numbers[th];
		}

		split(numbers, pivot_idx);

		if (th == left_arr.length)
			return numbers[pivot_idx];
		if (th < left_arr.length)
			return selection(left_arr, th);
		return selection(right_arr, th - left_arr.length - 1);
	}

	private static void split(Integer[] numbers, int pivot_idx) {
		List left = new ArrayList(pivot_idx);
		List right = new ArrayList(pivot_idx);
		int pivot = numbers[pivot_idx];
		for (int i = 0; i < numbers.length; i++)
			if (i != pivot_idx)
				if (numbers[i] < pivot)
					left.add(numbers[i]);
				else
					right.add(numbers[i]);
		left_arr = left.toArray(new Integer[0]);
		right_arr = right.toArray(new Integer[0]);

	}

	private static int conventional(Integer[] numbers, int th) {
		int min_idx;
		int min;
		for (int j = 0; j <= th; j++) {
			min_idx = j;
			min = numbers[min_idx];
			for (int i = j + 1; i < SIZE; i++)
				if (numbers[i] < min) {
					min = numbers[i];
					min_idx = i;
				}
			swap(numbers, j, min_idx);
		}

		return numbers[th];
	}

	private static void swap(Integer[] numbers, int idx, int i) {
		Integer temp = numbers[i];
		numbers[i] = numbers[idx];
		numbers[idx] = temp;
	}

	private static void populate(List list) {
		for (int i = 0; i < SIZE; i++)
			list.add(r.nextInt());
	}

}

a sample output, 1th algo is conventional sorting, 2th selection algorithm, 3th is in-place selection algorithm, 4th is merge-sort without Nth knowledge:

algo	th	size	time
1	8517	10000	203
2	8517	10000	0
3	8517	10000	0
4	8517	10000	0
1	6151	10000	171
2	6151	10000	0
3	6151	10000	0
4	6151	10000	0
1	6512	10000	141
2	6512	10000	0
3	6512	10000	0
4	6512	10000	0
1	5835	10000	125
2	5835	10000	16
3	5835	10000	0
4	5835	10000	0
1	7658	10000	140
2	7658	10000	0
3	7658	10000	0
4	7658	10000	16
1	3096	10000	62
2	3096	10000	0
3	3096	10000	0
4	3096	10000	0
1	9263	10000	156
2	9263	10000	0
3	9263	10000	0
4	9263	10000	0
1	279	10000	16
2	279	10000	0
3	279	10000	0
4	279	10000	0
1	2467	10000	62
2	2467	10000	0
3	2467	10000	0
4	2467	10000	0
1	9321	10000	172
2	9321	10000	0
3	9321	10000	0
4	9321	10000	0
1	4187	20000	219
2	4187	20000	0
3	4187	20000	0
4	4187	20000	15
1	17062	20000	594
2	17062	20000	0
3	17062	20000	0
4	17062	20000	15
1	19629	20000	610
2	19629	20000	859
3	19629	20000	0
4	19629	20000	0
1	8998	20000	406
2	8998	20000	0
3	8998	20000	0
4	8998	20000	16
1	4073	20000	203
2	4073	20000	0
3	4073	20000	15
4	4073	20000	0
1	5052	20000	266
2	5052	20000	0
3	5052	20000	0
4	5052	20000	0
1	12871	20000	531
2	12871	20000	0
3	12871	20000	0
4	12871	20000	16
1	8249	20000	390
2	8249	20000	16
3	8249	20000	0
4	8249	20000	0
1	13218	20000	547
2	13218	20000	0
3	13218	20000	0
4	13218	20000	15
1	11229	20000	485
2	11229	20000	0
3	11229	20000	0
4	11229	20000	15
1	19094	30000	1172
2	19094	30000	16
3	19094	30000	0
4	19094	30000	0
1	29685	30000	1391
2	29685	30000	0
3	29685	30000	0
4	29685	30000	15
1	22945	30000	1297
2	22945	30000	0
3	22945	30000	0
4	22945	30000	16
1	3061	30000	250
2	3061	30000	0
3	3061	30000	0
4	3061	30000	15
1	25646	30000	1360
2	25646	30000	15
3	25646	30000	0
4	25646	30000	0
1	6710	30000	515
2	6710	30000	0
3	6710	30000	0
4	6710	30000	16
1	27047	30000	1359
2	27047	30000	16
3	27047	30000	0
4	27047	30000	0
1	21610	30000	1296
2	21610	30000	16
3	21610	30000	0
4	21610	30000	16
1	4665	30000	359
2	4665	30000	16
3	4665	30000	0
4	4665	30000	0
1	10287	30000	766
2	10287	30000	0
3	10287	30000	0
4	10287	30000	15
1	33279	40000	2422
2	33279	40000	15
3	33279	40000	0
4	33279	40000	16
1	32581	40000	2359
2	32581	40000	16
3	32581	40000	0
4	32581	40000	15
1	9913	40000	1000
2	9913	40000	16
3	9913	40000	0
4	9913	40000	15
1	16908	40000	1562
2	16908	40000	16
3	16908	40000	0
4	16908	40000	16
1	35183	40000	2406
2	35183	40000	0
3	35183	40000	0
4	35183	40000	16
1	2418	40000	249
2	2418	40000	16
3	2418	40000	0
4	2418	40000	16
1	13714	40000	1328
2	13714	40000	15
3	13714	40000	0
4	13714	40000	16
1	33575	40000	2375
2	33575	40000	15
3	33575	40000	0
4	33575	40000	16
1	7649	40000	781
2	7649	40000	15
3	7649	40000	0
4	7649	40000	16
1	3952	40000	422
2	3952	40000	0
3	3952	40000	0
4	3952	40000	16
1	15863	50000	1953
2	15863	50000	0
3	15863	50000	16
4	15863	50000	15
1	34550	50000	3437
2	34550	50000	16
3	34550	50000	16
4	34550	50000	15
1	15782	50000	1953
2	15782	50000	16
3	15782	50000	0
4	15782	50000	16
1	35850	50000	3500
2	35850	50000	15
3	35850	50000	0
4	35850	50000	16
1	31501	50000	3312
2	31501	50000	16
3	31501	50000	0
4	31501	50000	31
1	125	50000	15
2	125	50000	16
3	125	50000	0
4	125	50000	16
1	4445	50000	594
2	4445	50000	16
3	4445	50000	0
4	4445	50000	15
1	36193	50000	3562
2	36193	50000	16
3	36193	50000	0
4	36193	50000	15
1	34106	50000	3437
2	34106	50000	16
3	34106	50000	15
4	34106	50000	16
1	21100	50000	2468
2	21100	50000	16
3	21100	50000	0
4	21100	50000	16
1	21830	60000	3140
2	21830	60000	0
3	21830	60000	16
4	21830	60000	15
1	37756	60000	4703
2	37756	60000	31
3	37756	60000	0
4	37756	60000	16
1	25114	60000	3531
2	25114	60000	0
3	25114	60000	0
4	25114	60000	31
1	39148	60000	4812
2	39148	60000	0
3	39148	60000	0
4	39148	60000	32
1	49241	60000	5374
2	49241	60000	16
3	49241	60000	15
4	49241	60000	16
1	4100	60000	671
2	4100	60000	0
3	4100	60000	0
4	4100	60000	32
1	42645	60000	5015
2	42645	60000	16
3	42645	60000	0
4	42645	60000	16
1	431	60000	62
2	431	60000	16
3	431	60000	0
4	431	60000	16
1	32025	60000	4219
2	32025	60000	31
3	32025	60000	0
4	32025	60000	31
1	7698	60000	1218
2	7698	60000	0
3	7698	60000	0
4	7698	60000	32
1	46123	70000	6593
2	46123	70000	0
3	46123	70000	0
4	46123	70000	31
1	31150	70000	5031
2	31150	70000	47
3	31150	70000	0
4	31150	70000	31
1	48965	70000	6922
2	48965	70000	15
3	48965	70000	16
4	48965	70000	15
1	38298	70000	5890
2	38298	70000	16
3	38298	70000	0
4	38298	70000	31
1	59441	70000	7374
2	59441	70000	15
3	59441	70000	16
4	59441	70000	16
1	52676	70000	7047
2	52676	70000	31
3	52676	70000	15
4	52676	70000	16
1	15627	70000	2796
2	15627	70000	32
3	15627	70000	15
4	15627	70000	16
1	59463	70000	7375
2	59463	70000	31
3	59463	70000	0
4	59463	70000	31
1	45982	70000	6577
2	45982	70000	32
3	45982	70000	0
4	45982	70000	31
1	12787	70000	2313
2	12787	70000	31
3	12787	70000	0
4	12787	70000	31
1	15160	80000	3281
2	15160	80000	0
3	15160	80000	0
4	15160	80000	31
1	63939	80000	9609
2	63939	80000	0
3	63939	80000	15
4	63939	80000	32
1	2078	80000	453
2	2078	80000	31
3	2078	80000	0
4	2078	80000	31
1	74875	80000	10014
2	74875	80000	32
3	74875	80000	0
4	74875	80000	32
1	56007	80000	8937
2	56007	80000	15
3	56007	80000	0
4	56007	80000	32
1	31383	80000	6015
2	31383	80000	32
3	31383	80000	0
4	31383	80000	31
1	27760	80000	5500
2	27760	80000	15
3	27760	80000	0
4	27760	80000	31
1	16742	80000	3624
2	16742	80000	0
3	16742	80000	16
4	16742	80000	31
1	26519	80000	5203
2	26519	80000	47
3	26519	80000	0
4	26519	80000	31
1	39750	80000	7234
2	39750	80000	15
3	39750	80000	0
4	39750	80000	32
1	52012	90000	10327
2	52012	90000	16
3	52012	90000	0
4	52012	90000	47
1	65039	90000	11608
2	65039	90000	16
3	65039	90000	0
4	65039	90000	47
1	80977	90000	12623
2	80977	90000	0
3	80977	90000	16
4	80977	90000	31
1	71638	90000	12123
2	71638	90000	16
3	71638	90000	0
4	71638	90000	47
1	9637	90000	2328
2	9637	90000	16
3	9637	90000	0
4	9637	90000	31
1	34558	90000	7484
2	34558	90000	16
3	34558	90000	0
4	34558	90000	31
1	19156	90000	4437
2	19156	90000	16
3	19156	90000	0
4	19156	90000	31
1	48443	90000	9750
2	48443	90000	15
3	48443	90000	0
4	48443	90000	31
1	56451	90000	10858
2	56451	90000	16
3	56451	90000	0
4	56451	90000	31
1	8441	90000	2062
2	8441	90000	0
3	8441	90000	16
4	8441	90000	31