Sequential Sort Algorithm

Question

I wanted to sort the elements that appear sequentially, i.e. I want my vector to be sorted before the next element appears. I know insertion sorting has n ^ 2 complexity if I have only n elements. Merging should be better. However, it is often said that merge sorting has complexity n log n; but I think this is true if you are going to sort n elements at once. If they come, instead, one by one, and you need a temporary vector to sort, the complexity increases to \ sum_ {i = 2} ^ n i log (i). This is still less than n ^ 2, I suppose, but definitely more than n log n.

Is it correct?

thanks

Answer 1

EDIT 2 :

\sum_{i=1}^N i log i > \sum_{i=1}^N i = O(N²) 

EDIT : Apparently you missed this, so I will try to clarify.

First, the insertion of N elements into the array, while sorting the array after each insertion can be performed according to complexity O (N²). You can use the following algorithm to insert a single element:

• Since the array is sorted, use a binary search to find the position at which the element is inserted. It takes O (log i) time, where i is the current size of the array.
• Insert an element by moving all the elements after it one spot to the right. This includes moving up to i elements, therefore O (i).

Repeating this algorithm for N inserts, we obtain \ sum_i (i + log i) = O (N²).

Make it very clear: this is not an insertion sort . Sorting an insert will involve sorting the entire array by reinstalling all the elements, while this algorithm simply inserts one element.

Secondly, this operation cannot be completed faster than O (N²): inserting one element into an array of size i, while sorting the array is more difficult than O (i), because it involves moving up to i elements. There is simply no way around this elementary fact: if you insert 1 into [2,3,..,i] , the result is [1,2,3,..,i] , which means that elements 2, 3 .. I need to transfer.

So, the sum is greater than \ sum_i i = O (N²).