sequential sorting algorithm

Question

I wanted to sort elements that come in sequentially, i.e., I want my vector to be sorted before the next element comes in. I know that insertion sort has complexity n^2, if I have a total of n elements. Merge sort should be better. However, it is often said that merge sort has complexity n log n; but I guess that is true if you are going to sort n elements at once. If they come, instead, one by one and you need the temporary vector to be sorted, the complexity goes up to \sum_{i=2}^n i log(i). This is still less than n^2 I presume, but definitely more than n log n.

Is that correct?

Thanks

Answer 1

EDIT 2:

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

EDIT: apparently, you missed the point, so I'll try to clarify.

First, inserting N elements into an array, while ensuring the array is sorted after every insert, can be done in complexity O(N2). You can use the following algorithm to insert one element:

• Since the array is sorted, use binary search to find the position where the element is inserted. Takes O(log i) time, where i is the current size of the array.
• Insert the element by moving all the elements after it one spot to the right. This involves moving up to i elements, so it's O(i).

Repeating this algorithm for N inserts thus yields \sum_i (i + log i) = O(N2).

To make it exceedingly clear : this is not insertion sort. Insertion sort would involve sorting the entire array by re-inserting all elements, while this algorithm merely inserts one element.

Second, doing this operation cannot be done faster than O(N2): inserting one element into an array of size i while keeping the array sorted is of complexity greater than O(i), because it involves moving around up to i elements. There is simply no workaround to circumvent this elementary fact: if you insert 1 into [2,3,..,i], the result is [1,2,3,..,i], which means elements 2, 3 .. i had to be moved.

So, the total is greater than \sum_i i = O(N2).

• zzzbbx: if you are talking about insertion sort, at each step you have i elements within the array, plus the one you want to insert. In the worst case scenario, it takes i steps to find the right spot. Hence, you have \sum_{i=1}^n i = O(n^2). The case with merge is different, because you can place the new element in front of the vector (or at the end of it) with complexity O(1), and then sort the all thing. This will give you \sum i log(i)
• zzzbbx: first of all, you are assuming insertion sort uses a binary tree internally to get O(i), otherwise the worst case scenario takes i steps, given that you don't know anything about the statistics of the elements coming in. secondly, if you have O(i) for each step, and n steps in total, you get O(1)+O(2)+...+O(n) = O(n^2)
• Victor Nicollet: @Banana: Everything you say about insertion sort is true, but completely irrelevant because the proposed algorithm is not insertion sort. This is an insert-item-into-sorted-array algorithm that works in O(i) worst-case (and O(1) best-case). Inserting N elements does have an O(N²) complexity, which is still smaller than using merge sort (or any sort, for that matter) after each insert.
• zzzbbx: in the standard literature, no mention about binary tree internally. Nonetheless, what you say about its complexity is correct, in the end it is O(n^2) and this is, by the way, how insertion sort works: it does what you said (look for right position, and insert element) every time. I was wrong about merge sort, since i log(i) is obviously at least n^2 if you sum up all contributions (although the moving stuff does not apply because you might append the element at the end, complexity one, or in front using a queue, before sorting)
• Victor Nicollet: @Banana: the "moving stuff" applies, because a sort will by its very definition move stuff around.