Balaji | Code

This algorithm performs sorting by splitting the input into two linked lists: asc_array (ascending) and dsc_array (descending).

Background

I wanted to design sorting algorithm. Since I can't solve everything in one attempt, I allowed myself to ignore time and space complexity in this version, and I used a few known techniques inside the flow when needed.

At a high level, this algorithm takes a different approach from traditional sorts: it begins by identifying the smallest and largest values and builds two linked lists from opposite ends - one in ascending order and one in descending order. Values that don't fit directly into either list are collected in a pending buffer, which is later inserted using a BST-guided strategy. Finally, both lists are merged to form the fully sorted output.

How It Works

1. Identify Min and Max

The algorithm first finds the minimum and maximum values in the input array. These two values become the starting points of the two linked lists:

asc_array starts with the minimum value.
dsc_array starts with the maximum value.

Then it loops through the remaining items. If the current index is the min or max index, it skips that item.

2. Distributing Elements into the Two Lists

For each item:

If the last item in asc_array is less than or equal to the current value, it belongs in the ascending list.
If the last item in dsc_array is greater than or equal to the current value, it belongs in the descending list.

If the item fits both conditions, it is appended to the list that is currently smaller. If both lists have the same size, it goes into asc_array.

If the item fits neither list, it is placed into pending_array.

3. The Pending Array

pending_array holds items that cannot be directly inserted into either linked list.

It uses a parameter called pending_item_percentage. This determines when the algorithm should process the pending items.

Formula:

pending_item_size = max(int(input_arr_len × pending_item_percentage), 6)

This ensures the pending list has a minimum size of 6, but can go up to a percentage of the total input size. When pending_array reaches this size, the algorithm processes all those items.

4. Processing Pending Items

When pending_array reaches the limit:

The algorithm selects the smaller of the two linked lists (asc_array or dsc_array).
It creates a temporary BST (binary search tree).
For each item in pending_array:
- It looks for the nearest value inside the BST.
- If that is not available, it starts from the tail of the chosen linked list and moves backward until it reaches the correct insertion point.
- The item is then inserted in order into the linked list.
- The BST stores the value along with a reference to the inserted linked-list node so that consecutive items can start from a closer position.

After all pending items are processed, the pending list becomes empty. If there are still leftover items at the end of the full array scan, the same process repeats.

5. Final Merge

Once all items are inserted, we have:

One sorted list in ascending order
One sorted list in descending order

The final step is similar to merge sort: Iterate through both lists simultaneously and merge them into one final sorted array.

Detailed Example: Step-by-Step Execution

Input Array:

[15, 3, 8, 1, 12, 6, 20, 4, 18, 2, 14, 10]

Configuration:

pending_item_percentage = 0.55

Phase 1: Initialization

Step 1.1 - Find Min and Max

Scanning the array:

min_value = 1   (index 3)
max_value = 20  (index 6)

Step 1.2 - Initialize Data Structures

asc_array = [1]        // ascending linked list
dsc_array = [20]       // descending linked list
pending_items = []
pending_item_size = max(int(12 × 0.55), 6) = 6

Initial State:

asc_array:      [1]
dsc_array:      [20]
pending_items:  []

Phase 2: Three-Way Streaming Classification

We iterate through the array, skipping indices of min (3) and max (6).

Index 0 → value = 15

Checks:

asc.last() = 1
dsc.last() = 20
1 ≤ 15 ≤ 20 → YES

Decision: fits middle band → append to smaller list
Sizes equal → append to asc_array

asc_array: [1, 15]
dsc_array: [20]
pending:   []

Index 1 → value = 3

Checks:

1 ≤ 3 ≤ 20 → NO
1 ≤ 3 → NO
20 ≥ 3 → YES

Decision: fits descending side only → append to dsc_array

asc_array: [1, 15]
dsc_array: [20, 3]
pending:   []

Index 2 → value = 8

Checks fail for both ends → add to pending

pending: [8]

Index 3 → value = 1 → SKIP (min)

Index 4 → value = 12

Fails all checks → pending

pending: [8, 12]

Index 5 → value = 6

Fails all checks → pending

pending: [8, 12, 6]

Index 6 → value = 20 → SKIP (max)

Index 7 → value = 4

Fails all checks → pending

pending: [8, 12, 6, 4]

Index 8 → value = 18

Checks:

15 ≤ 18 → YES
3 ≥ 18 → NO

Decision: fits ascending → append to asc_array

asc_array: [1, 15, 18]
pending:   [8, 12, 6, 4]

Index 9 → value = 2

Fits descending only → append to dsc_array

dsc_array: [20, 3, 2]

Index 10 → value = 14

Fails all checks → pending

pending: [8, 12, 6, 4, 14]

Index 11 → value = 10

Fails all checks → pending

pending: [8, 12, 6, 4, 14, 10]

Threshold reached!

len(pending) = 6 → processing required

Phase 3: BST-Accelerated Batch Insertion

Step 3.1 - Choose Target List

len(asc_array) = 3
len(dsc_array) = 3
→ equal → choose asc_array

Step 3.2 - Process pending items: [8, 12, 6, 4, 14, 10]

asc_array currently:

[1, 15, 18]

Important:

The BST is built incrementally during insertion. It stores the DATA VALUE as the key and the LINKED LIST NODE REFERENCE as the value. This helps find good starting points for subsequent insertions.

Insert 8

BST is currently empty
→ No hint available, start from tail (node containing 18)

Walk backward through linked list:
  Node(18): Is 18 ≥ 8? YES → move to prev
  Node(15): Is 15 ≥ 8? YES → move to prev
  Node(1):  Is 1 ≥ 8? NO → STOP

Insert 8 between Node(1) and Node(15)
Add to BST: BST[8] = reference to Node(8)

Result: [1, 8, 15, 18]

BST state: {8: Node(8)}

Insert 12

BST.find_nearest(12, find_smaller=False)
→ Searches BST for smallest value ≥ 12
→ BST currently has: {8}
→ 8 < 12, so no value ≥ 12 exists yet
→ Returns None

Since no hint, start from tail (node containing 18)

Walk backward:
  Node(18): Is 18 ≥ 12? YES → move to prev
  Node(15): Is 15 ≥ 12? YES → move to prev
  Node(8):  Is 8 ≥ 12? NO → STOP

Insert 12 between Node(8) and Node(15)
Add to BST: BST[12] = reference to Node(12)

Result: [1, 8, 12, 15, 18]

BST state: {8: Node(8), 12: Node(12)}

Insert 6

BST.find_nearest(6, find_smaller=False)
→ Searches for smallest value ≥ 6
→ BST has: {8, 12}
→ Smallest value ≥ 6 is 8
→ Returns Node(8) reference

Start from Node(8) 

Walk backward:
  Node(8): Is 8 ≥ 6? YES → move to prev
  Node(1): Is 1 ≥ 6? NO → STOP

Insert 6 between Node(1) and Node(8)

Add to BST: BST[6] = reference to Node(6)

Result: [1, 6, 8, 12, 15, 18]

BST state: {6: Node(6), 8: Node(8), 12: Node(12)}

Insert 4

BST.find_nearest(4, find_smaller=False)
→ Smallest value ≥ 4 is 6
→ Returns Node(6) reference

Start from Node(6):
  Node(6): Is 6 ≥ 4? YES → move to prev
  Node(1): Is 1 ≥ 4? NO → STOP

Insert 4 between Node(1) and Node(6)

Add to BST: BST[4] = reference to Node(4)

Result: [1, 4, 6, 8, 12, 15, 18]

BST state: {4, 6, 8, 12: Node refs}

Insert 14

BST.find_nearest(14, find_smaller=False)
→ Searches for smallest value ≥ 14
→ BST has: {4, 6, 8, 12}
→ All values < 14, no value ≥ 14 found
→ Returns None

Start from tail (Node 18):
  Node(18): Is 18 ≥ 14? YES → move to prev
  Node(15): Is 15 ≥ 14? YES → move to prev
  Node(12): Is 12 ≥ 14? NO → STOP

Insert 14 between Node(12) and Node(15)
Add to BST: BST[14] = reference to Node(14)

Result: [1, 4, 6, 8, 12, 14, 15, 18]

BST state: {4, 6, 8, 12, 14: Node refs}

Insert 10

BST.find_nearest(10, find_smaller=False)
→ Smallest value ≥ 10 is 12
→ Returns Node(12) reference

Start from Node(12) :
  Node(12): Is 12 ≥ 10? YES → move to prev
  Node(8):  Is 8 ≥ 10? NO → STOP

Insert 10 between Node(8) and Node(12)

Add to BST: BST[10] = reference to Node(10)

Result: [1, 4, 6, 8, 10, 12, 14, 15, 18]

BST state: {4, 6, 8, 10, 12, 14: Node refs}

How BST Optimization Helps:

Insert	Without BST	With BST Hint	Savings
8	Walk 3 nodes	Walk 3 nodes	0 (BST empty)
12	Walk 3 nodes	Walk 3 nodes	0 (no hint ≥12)
6	Walk 4 nodes	Walk 1 node	Saved 3 walks
4	Walk 5 nodes	Walk 1 node	Saved 4 walks
14	Walk 2 nodes	Walk 2 nodes	0 (no hint ≥14)
10	Walk 5 nodes	Walk 1 node	Saved 4 walks

Total walks: 22 nodes without BST → 11 nodes with BST = 50% reduction!

Step 3.3 - Clear pending buffer

pending_items = []

State after batch insertion:

asc_array: [1, 4, 6, 8, 10, 12, 14, 15, 18]
dsc_array: [20, 3, 2]

Phase 4: Final Processing

No pending items left.

Phase 5: Bidirectional Merge

Iterators:

asc_array → 1, 4, 6, 8, 10, 12, 14, 15, 18
dsc_array (reverse) → 2, 3, 20

Merge:

1 vs 2  → 1  
4 vs 2  → 2  
4 vs 3  → 3  
4 vs 20 → 4  
6 vs 20 → 6  
8 vs 20 → 8  
10 vs 20 → 10  
12 vs 20 → 12  
14 vs 20 → 14  
15 vs 20 → 15  
18 vs 20 → 18  
ASC done → take 20

Final Output

[1, 2, 3, 4, 6, 8, 10, 12, 14, 15, 18, 20]

Summary: What This Example Demonstrated

Phase	Example Showed
Initialization	Finding min=1, max=20 and creating dual sequences
Classification	Element 15 fitting middle zone (load balancing)
	Element 18 fitting ascending end only
	Element 2 fitting descending end only
	Elements 8,12,6,4,14,10 fitting neither (pending)
Batch Insertion	BST providing hints to reduce linked list walks
	Inserting 6 pending items into asc_array
	BST optimization: Insert 10 started from node(12), not tail
Merge	Bidirectional merge reading dsc_array backwards (2→3→20)

Time & Space Complexity

Time Complexity

Case	Complexity
Worst Case	O(n²)
Average Case	O(n log n)
Best Case	O(n)

Space Complexity

Metric	Complexity
Space	O(n)

GitHub →

⬇️ pip install bifurcated_sort

Bifurcated Insertion Sort

Background

How It Works

1. Identify Min and Max

2. Distributing Elements into the Two Lists

3. The Pending Array

4. Processing Pending Items

5. Final Merge

Detailed Example: Step-by-Step Execution

Phase 1: Initialization

Step 1.1 - Find Min and Max

Step 1.2 - Initialize Data Structures

Phase 2: Three-Way Streaming Classification

Index 0 → value = 15

Index 1 → value = 3

Index 2 → value = 8

Index 3 → value = 1 → SKIP (min)

Index 4 → value = 12

Index 5 → value = 6

Index 6 → value = 20 → SKIP (max)

Index 7 → value = 4

Index 8 → value = 18

Index 9 → value = 2

Index 10 → value = 14

Index 11 → value = 10

Phase 3: BST-Accelerated Batch Insertion

Step 3.1 - Choose Target List

Step 3.2 - Process pending items: [8, 12, 6, 4, 14, 10]

Insert 8

Insert 12

Insert 6

Insert 4

Insert 14

Insert 10

Step 3.3 - Clear pending buffer

Phase 4: Final Processing

Phase 5: Bidirectional Merge

Summary: What This Example Demonstrated

Time & Space Complexity