GATE Computer Science (CS) 2020 Solved Papers

Inserting an element at the beginning of the linked list takes O(1) time. But, If it needs to be sorted, then in the worst case, it takes (log n) time using merge sort. To insert such n elements and make sure it is in sorted order, the worst case time complexity would be O(n log n).