Question

Express the binary insertion sort in pseudocode.

Short answer

The pseudocode for the binary insertion sort is given as:

for k from 2 to n :

set i as 1

set j as k

while i < j :

set m as$\left[\frac{i+j}{2}\right]$

if arr[k] > arr[m]

set i as m + 1

else

set j as m

if arr[k] < arr[i]

set temp as arr[k]

for p from 0 to k - i - 1 :

arr[k - p] = arr[k - p -1]

set arr[i] as temp

return arr[e] for e = 1,2,3,....,n .

Step-by-step solution

Step 1:

• Binary insertion sort first compares the second element with the first element and places the second element as appropriate.
• On each comparison from now on, the current element is compared with the middle of the already sorted array and determines in which subinterval does the element lies.
• Done it repeatedly until the ideal position for each element occurs, and then insert the elements at their correct place.

Step 2:

The pseudocode for the binary insertion sort is given as:

for k from 2 to n :

set i as 1

set j as k

while i < j :

set m as$\left[\frac{i+j}{2}\right]$

if arr[k] > arr[m]

set i as m + 1

else

set j as m

if arr[k] < arr[i]

set temp as arr[k]

for p from 0 to k - i - 1 :

arr[k - p] = arr[k - p -1]

set arr[i] as temp

return arr[e] for e = 1,2,3,....,n .