List insert(int element, List lis) {
	if (lis.isEmpty()) {
		lis.add(0, new Integer(element));
		return lis;
	} else if (element > ((Integer) lis.get(0)).intValue()) {
		Integer first = (Integer) lis.get(0);
		List restList = new ArrayList();
		restList.addAll(insert(element, lis.subList(1,lis.size())));
		restList.add(0, first);
		return restList;
	} else {
		lis.add(0, new Integer(element));
		return  lis;
	}
}

List insertionsort(List lis) {
	if (lis.isEmpty()) return lis;
	else {
		List sorted = new ArrayList();
		sorted.addAll(insertionsort(lis.subList(1,lis.size())));
		return insert(((Integer) lis.get(0)).intValue(), sorted);
	}
}

NOT YET IMPLEMENTED IN Java

def flatten(lis)
	if lis.length == 0 then
		[]
	elsif lis[0].class != Array then
		[lis[0]] + flatten(lis[1..lis.length-1])
	else
		return flatten(lis[0]) + flatten(lis[1..lis.length-1])
	end
end

			
y = [5, 2, [16, [20, 1]], 30, [[[2]]]]
print flatten(y), "\n"

def partition(lis)
	part(lis[1..lis.length-1], lis[0])  #((<= part) part (> part)) will be returned
end

def part(lis, pivot)
	if lis.length==0 then
		[[]] + [pivot] + [[]]
	else
		r = part(lis[1..lis.length-1], pivot)    # recursive call which will
						 # return a list with structure
						  # ( (<= pivot) pivot (> pivot))
		#r
		if lis[0] > pivot then  # add to > list
			[r[0]] + [pivot] + [[lis[0]] + r[2]] 
		else  # add to <= list
			[[lis[0]] + r[0]] + r[1..r.length-1]
		end
	end
end
			
x = [6,3,4,9,10,1,7]
#OR from irb: partition(x) will print the answer as a list
print x, "\n"
#y = [1,2,10,12]
y = []
part(y,6)
#print partition(x), "\n"