binary insertion sort code in matlab

Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2(n)⌉ comparisons in the worst case, which is O(n log n). The algorithm as a whole still has a running time of O(n2) on average because of the series of swaps required for each insertion. The number of swaps can be reduced by calculating the position of multiple elements before moving them. For example, if the target position of two elements is calculated before they are moved into the right position, the number of swaps can be reduced by about 25% for random data. Write a program to simulate performance of BINARY INSERTION SORT.

Answer 1

[Ishaan Mehta]

Hi Saiteja

I understand that you want to implement Binary Insertion Sort, which is a variation of Insertion sort algorithm that uses binary search to find the appropriate index of the array elements.

Here is the code for the same:

x = [4 5 4 0 0 6 4 7 8 5 3 1];

sorted = binaryInsertionSort(x)

sorted = 1×12

0 0 1 3 4 4 4 5 5 6 7 8

function index = binarySearch(inArr, len, val)
    if len < 1
        index = 1;
        return;
    end

    l = 1;
    r = len;
    
    while l <= r
        mid = ceil((l + r) / 2);
        
        if inArr(mid) == val
            index = mid;
            return;
        else 
            if inArr(mid) > val
            r = mid - 1;
            else
                l = mid + 1;
            end
        end
    end

    index = l;
end


function sortedArray = binaryInsertionSort(inArray)
    sortedArray = inArray;
    n = length(inArray);

    for i = 1:n
        val = sortedArray(i); % get the current element
        pos = binarySearch(sortedArray, i-1, val); % find appropriate position for the current element
        sortedArray = [sortedArray(1:pos-1) val sortedArray(pos:end)]; % insert element in the appropriate position
        sortedArray(i+1) = []; % remove the current element, as its already inserted once in the last line
    end
end

Hope it helps

Ishaan Mehta