Jargon: Order Statistics problem is to find the kth smallest element in an unsorted array A[1..n]. This problem can be solved in O(n) time in average case using randomized select algorithm or in O(n) time in worst case time using an algorithm that chooses the pivot element carefully.
Problem: How to find second smallest element in an array A[1..n] of size n. We would like to do in much less than 2n comparisons.
Answer: Time Complexity = n + ceil(log n) - 2
Code for n + log n - 2 algorithm: second_smallest.py
Alternate implementation using linked list: second_smallest_linkedlist.py