sorting algorithm suitable for a sorted list

I have a sorted list at hand. Now i add a new element to the end of the list. Which sorting algorithm is su开发者_如何学Pythonitable for such scenario?

Quick sort has worst case time complexity of O(n²) when the list is already sorted. Does this mean time complexity if quick sort is used in the above case will be close to O(n²)?

---

If you are adding just one element, find the position where it should be inserted and put it there. For an array, you can do binary search for O(logN) time and insert in O(N). For a linked list, you'll have to do a linear search which will take O(N) time but then insertion is O(1).

As for your question on quicksort: If you choose the first value as your pivot, then yes it will be O(N²) in your case. Choose a random pivot and your case will still be O(NlogN) on average. However, the method I suggest above is both easier to implement and faster in your specific case.

---

It depends on the implementation of the underlying list. It seems to me that insertion sort will fit your needs except the case when the list is implemented as an array list. In this case too many moves will be required.

---

Rather than appending to the end of the list, you should do an insert operation.

That is, when adding 5 to [1,2,3,4,7,8,9] you'd result want to the "insert" by putting it where it belongs in the sorted list, instead of at the end and then re-sorting the whole list.

You can quickly find the position to insert the item by using a binary search.

This is basically how insertion sort works, except it operates on the entire list. This method will have better performance than even the best sorting algorithm, for a single item. It may also be faster than appending at the end of the list, depending on your implementation.

---

I'm assuming you're using an array, since you talk about quicksort, so just adding an element would involve finding the place to insert it (O(log n)) and then actually inserting it (O(n)) for a total cost of O(n). Just appending it to the end and then resorting the entire list is definitely the wrong way to go.

However, if this is to be a frequent operation (i.e. if you have to keep adding elements while maintaining the sorted property) you'll incur an O(n^2) cost of adding another n elements to the list. If you change your representation to a balanced binary tree, that drops to O(n log n) for another n inserts, but finding an element by index will become O(n). If you never need to do this, but just iterate over the elements in order, the tree is definitely the way to go.

Of possible interest is the indexable skiplist which, for a slight storage cost, has O(log n) inserts, deletes, searches and lookups-by-index. Give it a look, it might be just what you're looking for here.

---

What exactly do you mean by "list" ? Do you mean specifically a linked list, or just some linear (sequential) data structure like an array?

If it's linked list, you'll need a linear search for the correct position. The insertion itself can be done in constant time.

If it's something like an array, you can add to the end and sort, as you mentioned. A sorted collection is only bad for Quicksort if the Quicksort is really badly implemented. If you select your pivot with the typical median of 3 alogrithm, a sorted list will give optimal performance.