[]The time complexity of the number of comparisons in [half insertion sort]

# Half-fold insertion sort — the number of comparisons when inserting the Nth number. [Time complexity] O(nlog2(n)):

According to the algorithm idea, there are the following inferences:

Each number is inserted into the [depth]

of a decision tree at most , i.e. log2(n-1) (take the least positive integer) + 1

Analysis: Each comparison of the number inserted in the [ordered array] is compared with the number pointed to by Mid (Mid points to the middle position in the array to be compared). First, convert the ordered array into a binary tree form similar to a decision tree. The number of comparisons can only be up to the depth of this binary tree.

Example:

Suppose a set of ordered arrays: 1 2 3 4 5 6 7 8 9 (note that the already selected Mid will not be reselected)

First Mid: low=1, high=9, so Mid=(low+high)/2=5 Build the root of the binary tree ⑤

Second Mid: On the left of 5 low=1 high=4 Mid=(low+high)/2=2 On the right of 5 low=6 high=9 Mid=(low+high)/2=7 Continue to expand the binary tree ⑤ ② ⑦

Third Mid: On the left of 2 low=1 high=1 Mid=(low+high)/2=1 On the right of 2 low=3 high=4 Mid=(low+high)/2=3 On the left of 7 low=6 high=6 Mid=(low+high)/2=6 On the right of 7 low=8 high=9 Mid=(low+high)/2=8 Continue to expand the binary tree ⑤ ② ⑦ ① ③ ⑥ ⑧

Fourth Mid: On the right of 3 low=4 high=4 Mid=(low+high)/2=4 On the right of 8 low=9 high=9 Mid=(low+high)/2=9 Continue to expand the binary tree ⑤ ② ⑦ ① ③ ⑥ ⑧ ④ ⑨

Until all elements of the sorted array are present, the conversion is completed

(any sorted array can be converted into a binary tree in this way)

When inserting a 10: (the comparison is completed when there is no number to compare with it, the small left is the big right) ⑤ (Compare with 5 for the first time, and then compare the right side of 5 if it is greater than 5) ② ⑦ (Compare with 7 for the second time, and then compare the right side of 7 if it is greater than 7) ① ③ ⑥ ⑧ (comparison with 8 for the third time, and then compare the right side of 8 if it is greater than 8) ④ ⑨ (Compare with 9 for the fourth time. If it is greater than 9, then compare the right side of 9. If 9 has no right child, there is no need to compare it again. The comparison is complete) The number of comparisons is 4 According to the formula, log2(10-1) (take the least positive integer)+1=3+1=4

It can be seen that when inserting the Nth number into an ordered [array] , there are already N-1 numbers in the ordered array, and the number of comparisons can only be up to N-1 numbers that already exist in the ordered array **.** The depth of the binary tree into which 1 number is converted.

That is, log2(N-1) (take the least positive integer) + 1

The depth of a complete binary tree with n nodes is “log2n”+1

So the number of comparisons N < =log2(n-1) (take the least positive integer)+1 n-1 let i = n, ∑ = log2(1)+1+log2(2)+1+....+log2 (n-1)+1 i = 1 = log2[(n-1)! ]+n log2 [( n-1 ) when n is large ! ]≈ log2 ( n !) In the computer for the convenience of calculating log2 ( n !) ≈ n * log2 ( n ) log2 ( n !) is the same order of magnitude as n * log2 ( n )

**The total time complexity of the number of comparisons available is O(nlog2(n))**

The first time I write an article, it may not be correct. If there is any error, please point out, and my brother must change it.