How to keep a sorted list while entering data into it in Python

Question

I have a list of lists which need to be sorted based on the length of the lists. What I am doing now is first inserting the lists into the main list and then sort the main list giving key=len. This steps will take a total time of n + nlg(n). Is it possible to maintain a sorted list while entering the data into the main list? Can it be done using bisect (or is there any better way) and if so will it perform better thann + nlg(n)?

Answer 1

It depends on the data structure you are using:

• Dynamic Array
  • Finding the right index on a sorted array is O(log n) using a bisect
  • Inserting is O(n) as you have to shift everything
  • Total `O(n)
• Linked List
  • Finding the right index on a sorted linked list requires browsing the list until you get there. (O(n))
  • Inserting is a simple operation, takes only O(1).
  • Total O(n)
• Self-balancing BST
  • Inserting while maintaining the order and the balance is O(log n) amortized
  • There are links to implementations in this question
• Heap. Not exactly what you ask, but inserting into a heap is O(log n) or Theta(1) depending on the implementation you use. heapq in python is one implementation. You simple push items in your heap, and when you are done, you can get the sorted result in O(n). Meanwhile you can access the root of the tree in O(1), and the k smallest, sorted, in O(k).