In sorted order, still we have to traverse to the middle of linked list which takes O(n/2) which is O(n) only .
but, this can be made O(log n) by augmenting linked list with extra pointers like DLL, called skip list so that we can move in both the directions. which can give O(log n ) but not always, bcoz still worst is O(n).