# The time complexity of the number of comparisons in half insertion sort

[]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.