Binary Sort
- Binary Sort Algorithm
- Binary Sort Example
- Binary Sort Algorithm Implementation
- Binary Sort Algorithm Complexity
Binary sort is a comparison type sorting algorithm. It is a modification of the insertion sort algorithm. In this algorithm, we also maintain one sorted and one unsorted subarray. The only difference is that we find the correct position of an element using binary search instead of linear search. It helps to fasten the sorting algorithm by reducing the number of comparisons required.
Binary Sort Algorithm
Let us assume that we have an unsorted array A[]
containing n
elements. The first element, A[0]
, is already sorted and in the sorted subarray.
-
Mark the first element from the unsorted subarray
A[1]
as the key. -
Use binary search to find the correct position
p
ofA[1]
inside the sorted subarray. -
Shift the elements from
p
1 steps rightwards and insertA[1]
in its correct position. -
Repeat the above steps for all the elements in the unsorted subarray.
Binary Sort Example
Suppose we have the array: (5,3,4,2,1,6)
. We will sort it using the insertion sort algorithm.
Sorted subarray | Unsorted Subarray | Array |
---|---|---|
( 5 ) | ( 3, 4, 2, 1, 6) | (5, 3, 4, 2, 1, 6) |
- First Iteration
Key : A[1]
= 3
Binary Search: returns the position of 3
as index 0
. Right shift rest of elements in the sorted array.
Sorted subarray | Unsorted Subarray | Array |
---|---|---|
( 3 , 5) | (4, 2, 1, 6) | (3, 5, 4, 2, 1, 6) |
- Second Iteration
Key : A[2]
= 4
Binary Search: returns the position of 4
as index 1
. Right shift rest of elements in the sorted array.
Sorted subarray | Unsorted Subarray | Array |
---|---|---|
( 3, 4, 5) | (2, 1, 6) | (3, 4, 5, 2, 1,6) |
- Third Iteration
Key : A[3]
= 2
Binary Search: returns the position of 2
as index 0
. Right shift rest of elements in the sorted array.
Sorted subarray | Unsorted Subarray | Array |
---|---|---|
( 2, 3, 4, 5) | (1, 6) | (2, 3, 4, 5, 1,6) |
- Fourth Iteration
Key : A[4]
= 1
Binary Search: return the position of 1
as index 0
. Right shift rest of elements in the sorted array.
Sorted subarray | Unsorted Subarray | Array |
---|---|---|
( 1, 2, 3, 4, 5) | (6) | (1, 2, 3, 4, 5, 6) |
- Fifth Iteration
Key : A[5]
= 6
Binary Search: return the position of 6
as index 5
. There are no elements on the right side.
Sorted subarray | Unsorted Subarray | Array |
---|---|---|
( 1, 2, 3, 4, 5, 6) | () | (1, 2, 3, 4, 5, 6) |
We get the sorted array after the fourth iteration - (1 2 3 4 5 6)
Binary Sort Algorithm Implementation
#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";
}
Binary Sort Algorithm Complexity
Time Complexity
- Average Case
Binary search has logarithmic complexity logn
compared to linear complexity n
of linear search used in insertion sort. We use binary sort for n
elements giving us the time complexity nlogn
. Hence, the time complexity is of the order of [Big Theta]: O(nlogn)
.
- Worst Case
The worst-case occurs when the array is reversely sorted, and the maximum number of shifts are required. The worst-case time complexity is [Big O]: O(nlogn)
.
- Best Case
The best-case occurs when the array is already sorted, and no shifting of elements is required. The best-case time complexity is [Big Omega]: O(n)
.
Space Complexity
Space Complexity for the binary sort algorithm is O(n)
because no extra memory other than a temporary variable is required.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn