Suppose binary sort is still a new concept to you; check out this post now. It covers all the most basic information about this algorithm.

Binary sort is among well-known comparison-style sorting algorithms, which is an alteration of insertion sorting algorithm. We may also retain an unsorted and a sorted subarray in the algorithm.

The sole distinction is that binary search is used to determine an element’s precise position rather than linear search. By lowering the necessary comparisons, it aids in speeding up the sorting algorithm.

Binary Sorting Algorithm

Let’s say we have the A[] unsorted array with the entries n. The sorted subarray contains the first component A[0], which is sorted already.

• Make the first component A[1] the key in the unsorted subarray.
• To locate the A[1]’s correct p location within your sorted subarray, utilize binary search.
• Move the components starting at p one step to the right, then insert component A[1] where it belongs.
• Follow the same procedure as before for each element of the un-sorted subarray.

Example Of Binary Sort

Take the (5,3,4,2,1,6) array as an example. We’ll use an insertion sort technique to sort it.

• Iteration number 1

Key: A[1] = 3

Binary Search: gives back the 3 position as 0 index. The remaining array elements are shifted to the right.

• Iteration number 2

Key: A[2] = 4

Binary Search: gives back the 4 position as 1 index. The remaining array elements are shifted to the right.

• Iteration number 3

Key: A[3] = 2

Binary Search: gives back the 2 position as 0 index. The remaining array elements are shifted to the right.

• Iteration number 4

Key: A[4] = 1

Binary Search: gives back the 1 position as 0 index. The remaining array elements are shifted to the right.

• Iteration number 5

Key: A[5] = 6

Binary Search: gives back the 6 position as 5 index. The right side is empty.

After iteration number 4, we obtain the (1 2 3 4 5 6) sorted array.

Implement Binary Sorting Algorithm

You can use the following implementation as a reference.

#include<bits/stdc++.h>
using namespace std;

int binarySearch(int a[], int x, int low, int high)
{
    if (high <= low)
        return (x > a[low]) ?
               (low + 1) : low;
    int mid = (low + high) / 2;
    if (x == a[mid])
        return mid + 1;
    if (x > a[mid])
        return binarySearch(a, x,
                            mid + 1, high);

    return binarySearch(a, x, low,
                        mid - 1);
}

void binarySort(int a[], int n)
{
    for (int i = 1; i < n; ++i)
    {
        int j = i - 1;
        int key = a[i];
        int pos = binarySearch(a, key, 0, j);

        while (j >= pos)
        {
            a[j + 1] = a[j];
            j--;
        }

        a[j + 1] = key;
    }
}

int main() {
    int n = 6;
    int arr[6] = {5, 3, 4, 2, 1, 6};
    cout << "Input arr: ";

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    cout << "\n";
    binarySort(arr, n); // Sort elements in ascending order
    cout << "Output arr: ";

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    cout << "\n";
}

Complexity Of Binary Sorting Algorithm

Complexity Of Time

• Average Scenario

In comparison to the n linear complexity of the linear search employed in the insertion sort, binary search has a logn logarithmic complexity. For the elements n, we utilize binary sort, which provides the nlogn time complexity. Because of this, the complexity of time is [Big Theta]: O(nlogn).

• Worst Scenario

This happens once an array is reverse-sorted while the greatest amount of shifts are necessary. Time complexity’s worst scenario is [Big O]: O(nlogn).

• Best Scenario

Since an array is sorted, no element shifting is necessary in the best scenario. Time complexity’s best scenario is [Big Omega]: O(n).

Space Complexity

Because the binary sorting method only needs a nonpermanent variable as additional memory, its space complexity is O(n).

The Bottom Line

Above are the fundamentals of the binary sort that you need to know. Hopefully, this post has cleared out your confusion about this algorithm.If you want to learn more binary-related skills in programming languages, check out this guide on converting int to binary in Python.