Monday, February 23, 2026

Parity-Binary Sort (Super Easy in Python)

Index of "Algorithms: Design and Analysis"
<<< Previous Next >>>

Basic Programming> Bit Manipulation> Basics of Bit Manipulation

Problem

You are given an array $A$ of $N$ integers. Your task is to implement a sorting algorithm that arranges the numbers in the array based on following conditions and return that array:
1. Numbers with an even count of set bits should appear first in ascending order.
2. Following that, numbers with an odd count of set bits should be arranged in ascending order.

Input Format:

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

The first line contains $T$ denoting the number of test cases. $T$ also specifies the number of times you have to run the solve function on a different set of inputs.
For each test case:

The first line contains the integer $N$ .
The second line contains the array $A$ of length $N$

Output Format:
For each test case, print the answer in a new line.

Constraints:

$1 \leq T \leq 10 \\ 1 \leq N \leq 10^5 \\ 1 \leq A[i] \leq 10^5$

Sample Input

1
6
5 2 8 12 7 6

Sample Output

5 6 12 2 7 8

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

Given the input array [5, 2, 8, 12, 7, 6], the output should be [5, 6, 12, 2, 7, 8], as:
Numbers with an even count of set bits: 5(101), 6(110), 12(1100)
Numbers with an odd count of set bits: 2(10), 7(111), 8(100)

Contributers:

Vinayak Mishra

Madhumeeta Bauk

My Code

def solve(A):
    evens = [i for i in A if i.bit_count() % 2 == 0]
    odds = [i for i in A if i.bit_count() % 2 != 0]

    evens.sort()
    odds.sort()

    final = evens + odds
    return ' '.join(map(str, final))

T = int(input())

for _ in range(T):
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(A))

Revising Binary Sort (Though we used Python built-in in the code)

help me revise binary sort algorithm

Sure 👍 Let’s revise Binary Sort properly and clearly.

But first — when people say Binary Sort, they usually mean one of these two things:

Binary Insertion Sort (Insertion sort optimized using Binary Search)
Sorting Binary Array (0s and 1s only)

I’ll cover both so you're fully prepared for interviews and DSA practice.

1️⃣ Binary Insertion Sort (Important for DSA)

🔹 Idea

Normal Insertion Sort:

Pick element
Compare backwards
Shift elements
Insert at correct place

Binary Insertion Sort:

Use Binary Search to find correct position
Still shift elements manually

⚠ Important:

Comparisons reduce to O(n log n)
But shifting still makes overall complexity O(n²)

🔹 Algorithm Steps

For each element from index 1 → n-1:

Store current element as key
Use binary search in sorted portion [0 … i-1]
Find correct index pos
Shift elements right
Insert key at pos

🔹 Example

Array:

Code
[5, 2, 4, 6, 1]

Step 1:
Sorted part: [5]
Insert 2 → Binary search → position 0
Array → [2, 5, 4, 6, 1]

Step 2:
Sorted part: [2, 5]
Insert 4 → position 1
Array → [2, 4, 5, 6, 1]

Continue...

Final:

Code
[1, 2, 4, 5, 6]

🔹 Python Implementation

Python
def binary_search(arr, key, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] > key:
            end = mid - 1
        else:
            start = mid + 1
    return start

def binary_insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        pos = binary_search(arr, key, 0, i - 1)
        
        # shift elements
        arr = arr[:pos] + [key] + arr[pos:i] + arr[i+1:]
        
    return arr

🔹 Time Complexity

Case	Complexity
Best	O(n log n) comparisons
Worst	O(n²) shifts
Overall	O(n²)

2️⃣ Sorting Binary Array (0s and 1s Only)

If array contains only 0 and 1:

Example:

Code
[1, 0, 1, 0, 0, 1]

Method 1: Counting (Simple)

Python
def sort_binary(arr):
    count_zero = arr.count(0)
    return [0]*count_zero + [1]*(len(arr) - count_zero)

Time: O(n)

Method 2: Two Pointer (Interview Favorite)

Python
def sort_binary(arr):
    left = 0
    right = len(arr) - 1
    
    while left < right:
        if arr[left] == 1:
            arr[left], arr[right] = arr[right], arr[left]
            right -= 1
        else:
            left += 1
    
    return arr

Time: O(n)
Space: O(1)

🧠 When Is Binary Insertion Sort Useful?

When comparisons are very expensive
When dataset is small
When array is almost sorted
Used internally in hybrid algorithms (like Timsort conceptually)

🔥 Interview Summary Answer

If interviewer asks:

What is Binary Sort?

You say:

Binary Insertion Sort is an optimization of insertion sort where we use binary search to find the correct position of an element in the sorted part of the array. It reduces comparisons to O(n log n) but shifting still makes overall time complexity O(n²).

If you'd like, I can:

🔹 Compare it with Merge Sort / Quick Sort
🔹 Give dry run practice questions
🔹 Give optimized in-place version
🔹 Explain mathematically why it’s still O(n²)

What level are you preparing for — college exam, coding round, or advanced DSA?

Explain mathematically why it’s still O(n²)

Great — this is the exact kind of thinking interviewers love. Let’s break it down mathematically and cleanly.

We’re analyzing Binary Insertion Sort.

🔎 Step 1: What Actually Changes?

Normal Insertion Sort:

Find correct position → O(i) comparisons
Shift elements → O(i)

Binary Insertion Sort:

Find position using binary search → O(log i) comparisons
Shift elements → O(i)

So only comparisons improve, not shifting.

🔎 Step 2: Count Total Work Precisely

For an array of size n.

At step i, worst case:

Binary search cost = O(log i)
Shifting cost = O(i)

Total cost at step i:

Code
T(i) = log i + i

🔎 Step 3: Total Cost Over All Iterations

We sum from i = 1 to n-1.

T(n) = \sum_{i=1}^{n-1} (\log i + i)

Break into two sums:

T(n) = \sum \log i + \sum i

Part A: Sum of log i

\sum_{i=1}^{n} \log i = \log(n!)

Using Stirling’s approximation:

\log(n!) ≈ n \log n

So:

\sum \log i = O(n \log n)

Part B: Sum of i

\sum_{i=1}^{n} i = \frac{n(n+1)}{2}

Which simplifies to:

O(n^2)

🔎 Step 4: Combine Both

T(n) = O(n \log n) + O(n^2)

Now compare growth rates:

n^2 \gg n \log n

As n becomes large:

\frac{n^2}{n \log n} = \frac{n}{\log n} \to \infty

So n² dominates.

✅ Final Mathematical Conclusion

T(n) = O(n^2)

Because:

Comparisons = O(n log n)
Shifting = O(n²)
Dominant term = O(n²)

🧠 Intuition (Very Important)

Binary search helps you find where to insert.

But it does NOT help you move elements.

In an array:

To insert at index 0, you must shift n elements.

That physical movement costs linear time.

And that happens n times.

So:

n \times n = n^2

🔥 Interview One-Liner

Even though binary search reduces comparisons to O(n log n), insertion still requires shifting elements which costs O(n) per iteration. Summing over all iterations gives O(n²), which dominates the total complexity.

If you'd like, I can now:

Prove why linked list version behaves differently
Compare with Merge Sort mathematically
Show graphical growth comparison
Or derive the exact average-case complexity mathematically

What depth are you aiming for?

survival8

Pages