Comparing sorting algorithms when the data items are incoming rather than being present already -

i @ intermediate level in algorithms. when comparing different sorting algorithms thing stuck me.

how compare different sorting algorithms when data rather incoming being present?

i have compared few myself not sure if right approach.

insertion sort : name suggests, presents nice solution problem o(n^2) complexity.

heap sort : technique build heap each data item pushed. corresponds sift-up operation o(logn) complexity , exchange first element last element , heapify restore heap properties. heapify again o(logn) overall complexity o(n logn logn). if have data items present o(n logn) because doing heapify operation on data items after have built heap.

selection sort : needs data items before sorting, assume there no solution our problem using selection sort.

tree sort : dominant step in technique build tree has worst-case time complexity of o(n^2). , in-order traversal do.

i not sure other algorithms.

i posting question looking complete hold on these sorting techniques. pardon me if find discrepancies in either question or comparisons.

building heap 1 item @ time doesn't add complexity (and o(n log n log n) doesn't make sense me @ all). in fact, normal way build heap add 1 item @ time heap anyway. say, if have items available start with, start building heap of first two, adding third, fourth, , on. if you're receiving items 1 @ time, doesn't cause any work @ all. ends o(n log n), always.

just clear: swapping item first position , sifting tree not when you're adding items -- it's when you're removing items. say: when you're done inserting items heap, you're reading produce sorted output. swapping item @ base of heap (i.e., first item in array) end of array, taking item started out @ end of array, , sifting upward in heap until heap property restored.

when you're adding new items heap, add them @ end, sift them downward restore heap property. in typical case they're available, starting @ beginning of array, , having partition between items form heap, , items still jumbled mess. build items heap, move partition on 1 item, sift item down belongs, , repeat. "online" version doesn't have data available, changes after sift item heap, have wait next item arrive before sift heap (where you'd insert next item immediately).

building tree o(n²) if 1) items arrive ordered, , 2) don't realize that, , 3) don't re-balance tree build it. if items in random order start with, without balancing, complexity close o(n log n). in typical case of building red-black or avl tree, it'll remain o(n log n) if items in order (though o(n log n) lower constants if arrive in more or less random order instead of sorted). likewise, if use b-tree, you'll o(n log n) complexity, if data arrive in order.