Deferred Algorithmic Improvements and Technical Debt

# Deferred Algorithmic Improvements and Technical Debt

## Status

**Deferred / paused for now.**

LayerKeySort v1.0.0 is currently considered functionally complete enough to pause development while attention moves to other projects.

This issue exists to preserve the important algorithmic findings, limitations, potential bugs, and future design directions discovered after the v1.0.0 release.

The goal is **not** to implement these changes immediately.

When development resumes, this issue should be treated as the starting point for the next algorithm-focused phase.

---

# 1. Current project positioning

LayerKeySort should currently be understood primarily as:

> A stable C17 ordering library that combines comparator-based ordering, hierarchical Path positions, Tree-based placement, independently constructed Groups, and stable Group merging.

It should **not currently be presented as a general-purpose replacement for `qsort`, mergesort, quicksort, or other conventional sorting algorithms**.

The strongest idea in the project is not raw sorting speed.

The more distinctive capability is that an item's ordered position is represented explicitly by a hierarchical `LksPath`.

Conceptually:

```text
input
  ↓
comparator
  ↓
locate ordered position
  ↓
generate Path
  ↓
insert into Tree
  ↓
produce ordered Group
```

For batch operation:

```text
input
  ↓
split into Groups
  ↓
build local ordering + local Paths
  ↓
stable pairwise merge
  ↓
preserve Base Paths
  ↓
re-encode Incoming Paths
  ↓
final ordered Group
```

This means LayerKeySort currently sits closer to an **ordering / order-maintenance system with explicit position labels** than to a conventional one-shot array sorting routine.

---

# 2. Important design strength to preserve

Future optimization must not accidentally remove the properties that make LayerKeySort interesting.

The following behaviors should be treated as core design constraints unless deliberately redesigned.

## 2.1 Stable ordering

Comparator-equal elements preserve source order.

For normal item insertion:

```text
5a
5b
5c
```

followed by another equal item:

```text
5d
```

should result in:

```text
5a
5b
5c
5d
```

The current implementation explicitly walks the comparator-equal run before assigning a new Path.

---

## 2.2 Stable Group merging

For:

```text
Base
Incoming
```

comparator-equal items from `Base` are ordered before comparator-equal items from `Incoming`.

Ordering inside each original source is also preserved.

For `GroupBatch`, chunk/source ordering for equal items must remain stable across the full merge process.

---

## 2.3 Explicit Path positions

A Path is not merely an implementation detail.

A Path represents an explicit ordered position.

Examples:

```text
000
0A3
0A3//A0
0A3/A0
0A4
```

Hierarchical depth and skipped levels make it possible to represent new positions between existing positions.

This is one of the main features that distinguishes LayerKeySort from ordinary sorting libraries.

---

## 2.4 Caller-owned items

LayerKeySort owns structural data but does not own caller business objects.

The current ownership contract should remain clear:

```text
caller owns item
LayerKeySort borrows item pointer

LayerKeySort owns:
- Paths
- Tree nodes
- Group structural storage
- Batch structural storage
```

---

## 2.5 Failure behavior

The current code has substantial allocation-failure testing.

Future rewrites should preserve strong failure guarantees where currently documented, especially:

- output remains `NULL` on failed public constructors/build operations;
- public merge does not corrupt its inputs;
- allocation failure does not silently produce partially valid objects;
- no memory leaks after failure;
- caller-owned items are never destroyed by LayerKeySort.

---

# 3. Main algorithmic issue: uncontrolled Path growth

This is currently the most important architectural limitation.

## 3.1 Sequential append behavior

`lks_path_after()` currently tends to generate a new ordered position by cloning the existing Path and appending another step.

Conceptually, repeated increasing insertion may evolve approximately like:

```text
ZERO

A0

A0/A0

A0/A0/A0

A0/A0/A0/A0

...
```

For `n` monotonically increasing items, Path depth may therefore grow approximately with item position:

```text
depth(i) = O(i)
```

The total number of stored Path steps may approach:

```text
0 + 1 + 2 + ... + (n - 1)
```

which is:

```text
n(n - 1) / 2
```

therefore:

```text
O(n²)
```

Path-storage growth in pathological insertion orders is therefore a major concern.

---

# 4. Existing benchmark evidence of the Path-growth problem

The repository already contains a useful pathological regression case.

A benchmark constructs:

```c
for (i = 0; i < 1024; ++i) {
    values[i] = (int)i;
}
```

with:

```text
N = 1024
GroupSize = 1
```

The currently frozen regression values include approximately:

```text
ComparatorCount = 14337
ResultOnlyBytes  = 5339184
PeakBytes        = 14744752
```

This is valuable evidence.

It does **not** mean that LayerKeySort always consumes this much memory.

Random data and grouped input can behave much better.

However, it demonstrates that ordered / singleton-style construction can produce severe structural expansion.

This case should remain as a permanent regression case after any future redesign.

---

# 5. Comparator count is not sufficient for performance analysis

A relatively low comparator count can make the algorithm look more efficient than it really is.

Current benchmark counters mainly count business-item comparator invocations:

```c
compare(left_item, right_item, context)
```

But significant work also occurs in:

- Path comparison;
- Path consistency validation;
- Path cloning;
- Path allocation;
- Path step copying;
- prefix Path construction;
- Tree prefix lookup;
- child binary searches;
- `memmove` of child arrays;
- allocation/reallocation;
- flattening;
- rebuilding ordered views.

Therefore:

```text
low comparator count
```

does **not** necessarily mean:

```text
low total runtime complexity
```

Future benchmarks should separately measure structural work.

---

# 6. Potential severe worst-case time complexity

This needs formal analysis when development resumes.

A Path of depth `d` may require prefix traversal during explicit Tree insertion.

The current implementation repeatedly constructs/searches prefixes.

At different stages it can compare Paths whose lengths themselves depend on `d`.

This creates the possibility of work similar to:

```text
1 + 2 + 3 + ... + d
```

for a deep Path insertion:

```text
O(d²)
```

If pathological sequential insertion causes:

```text
d = O(n)
```

then insertion cost may potentially become:

```text
O(n²)
```

and building `n` items may approach:

```text
O(n³)
```

in Path-related work.

This is a worst-case structural concern, not yet a formal complete proof of the entire implementation's exact complexity.

It should be investigated explicitly.

A future algorithm analysis should separately derive:

- comparator complexity;
- Path comparison complexity;
- Tree-navigation complexity;
- allocation complexity;
- Path-copy complexity;
- worst-case total complexity.

---

# 7. Reverse-order degeneration is different

Increasing input is not the only problematic distribution.

Repeated insertion toward the opposite side may produce many siblings rather than a deep Path chain.

Children are currently represented as ordered pointer arrays.

Insertion may require:

```c
memmove(...)
```

to shift following child pointers.

Repeated front insertion can therefore cause cumulative movement similar to:

```text
1 + 2 + 3 + ... + n
```

which gives:

```text
O(n²)
```

pointer movement.

Therefore the current implementation is sensitive to input ordering in more than one way.

Potential distributions to analyze separately:

```text
Sorted ascending
Sorted descending
All equal
Heavy duplicate
Random unique
Random duplicate
Nearly sorted
Organ-pipe
Alternating low/high
Repeated insertion into the same narrow gap
```

---

# 8. All-equal data is especially important

All-equal input stresses several important mechanisms simultaneously:

- stability;
- equal-run traversal;
- repeated insertion after existing equal items;
- Path growth;
- successor lookup;
- memory growth.

The current property stress suite intentionally limits some distributions:

```text
All Equal       <= 64
Heavy Duplicate <= 96
Duplicate       <= 192
```

while general stress may reach:

```text
N = 512
```

These tests are useful for correctness but are not large enough to establish scalability for the most dangerous distributions.

Future stress testing should include large all-equal cases.

Suggested sizes:

```text
1,000
10,000
100,000
```

and higher only if practical.

---

# 9. Random-data scalability is much better and should remain part of the comparison

The algorithm should not be described as universally memory-expensive.

The repository also contains larger random/grouped regression cases.

For example, the frozen validation includes approximately:

```text
N = 10000
Groups = 32
Seed = 0xC0FFEE

ResultOnlyBytes = 1603160
OverallPeakBytes = 4434688
```

This is dramatically better than the pathological singleton/ordered case on a per-item basis.

Therefore the real problem is better described as:

> Path size and structure currently have poor worst-case control and are strongly dependent on insertion distribution.

This distinction should be preserved in future documentation.

---

# 10. Highest-priority future algorithm work: redesign endpoint Path allocation

The most important algorithmic improvement is likely to be changing how new positions are generated before/after an existing endpoint.

Current conceptual behavior:

```text
A0
A0/A0
A0/A0/A0
A0/A0/A0/A0
```

Possible improved strategy:

```text
A0
A1
A2
A3
...
```

Only increase Path depth when the current level has no suitable remaining position.

The slot space already contains:

```text
A0 ... Z9
```

which gives 260 slot values.

Sequential append operations should ideally consume available same-level coordinate space before increasing depth.

Goals:

- avoid linear Path-depth growth on repeated append;
- reduce memory use;
- reduce Path comparison cost;
- reduce prefix lookup cost;
- keep Paths human-readable;
- preserve stable ordering.

---

# 11. Consider wider-gap allocation

A simple "`A0`, `A1`, `A2`..." strategy may still eventually exhaust local space.

A better allocator could intentionally leave gaps.

For example:

```text
A0
A8
AG
AO
...
```

or another deterministic spacing policy.

Then later insertion between positions has room without immediate deeper encoding.

Possible approaches to research:

- midpoint allocation;
- fractional indexing;
- lexicographic variable-length indexing;
- order-maintenance labels;
- deterministic sparse slot allocation;
- periodic relabeling;
- batch gap allocation.

The goal is not necessarily to copy any existing system, but established work should be studied before designing the next Path allocator.

---

# 12. Research references / concepts for future work

Before redesigning Path allocation, investigate existing order-maintenance techniques.

Relevant topics:

```text
Order Maintenance Problem
Fractional Indexing
Lexicographic order keys
CRDT sequence identifiers
List labeling
Dietz-Sleator order maintenance
Bender et al. order maintenance
LexoRank-style approaches
```

The conceptual problem is:

> Maintain stable relative order while allowing new identifiers to be generated between existing identifiers without frequent global renumbering.

LayerKeySort's Path system is one solution attempt to this problem family.

Future documentation should avoid claiming that the broad concept itself is entirely novel.

The novel part, if any, should instead be described precisely in terms of LayerKeySort's specific encoding / Tree / Group / merge behavior.

---

# 13. Consider separating Path representation from Tree topology

Currently Path hierarchy strongly influences actual Tree hierarchy.

This creates an important coupling:

```text
long Path
    ↓
deep Tree relationship
    ↓
more traversal / prefix work
```

Future architecture should consider treating Path purely as an order label.

The search/index structure could then be independent.

Possible index structures:

```text
balanced binary search tree
B-tree
skip list
sorted vector + index
treap
red-black tree
AVL tree
other order-statistics structure
```

Conceptually:

```text
Path = position identifier

Index structure = efficient lookup/navigation
```

instead of:

```text
Path hierarchy == physical Tree hierarchy
```

This may substantially improve worst-case behavior.

However, this is a major architectural change and should not be attempted without a clear compatibility plan.

---

# 14. Consider Path depth limits and relabeling

Unlimited Path growth is undesirable.

A future design could define:

```text
soft maximum depth
hard maximum depth
```

When a local area exceeds the soft limit, the implementation could rebalance / relabel part of the structure.

Possible strategy:

```text
detect dense/deep region
    ↓
collect local ordered run
    ↓
assign new sparse Paths
    ↓
replace Paths atomically
```

Important questions:

- Are Paths supposed to remain stable forever?
- May existing Paths change after insertion?
- Are external users allowed to persist Paths?
- Are Paths only local coordinates?
- Can relabeling be observable?

This requires deciding the semantic role of `LksPath`.

---

# 15. Clarify whether Path identity is persistent or ephemeral

Current documentation says Paths represent ordering positions and are local to their Group/Tree.

This suggests Paths may be structural rather than durable external IDs.

If so, future relabeling may be acceptable.

If applications are expected to persist or externally reference Paths, relabeling becomes much harder.

Before implementing automatic rebalance, explicitly decide:

```text
Are Paths stable identities?

or

Are Paths replaceable order coordinates?
```

This decision affects almost every future optimization.

---

# 16. Possible API contract issue: negative-to-positive `lks_path_between`

The public API currently describes:

```c
lks_path_between(left, right, &out_path)
```

as allocating a Path strictly between two ordered Paths.

However, the current implementation rejects:

```text
NEGATIVE < POSITIVE
```

directly with:

```text
LKS_STATUS_INVALID_ARGUMENT
```

even though:

```text
NEGATIVE < ZERO < POSITIVE
```

and therefore ZERO is mathematically a valid position between them.

This should be investigated.

Possible outcomes:

## Option A — implementation bug

If the contract means:

> any two valid ordered Paths

then:

```text
negative → positive
```

should probably return a zero Path.

---

## Option B — intentional restriction

If `lks_path_between()` is only meant for certain structurally adjacent Path classes, then the public API documentation needs to state the restriction explicitly.

Regardless of the final decision, add dedicated tests.

Suggested regression:

```c
negative = ...
positive = ...

assert(lks_path_compare(negative, positive) < 0);

status = lks_path_between(negative, positive, &middle);
```

Then verify the intended contract.

---

# 17. API wording issue: "immediately before / after"

Current documentation uses wording such as:

```text
immediately before RIGHT
immediately after LEFT
```

For a dense Path order where another position can always potentially be generated between two existing positions, there may not be a mathematical "immediate successor" or "immediate predecessor."

More precise wording could be:

```text
Generate a valid position before RIGHT.
Generate a valid position after LEFT.
```

or:

```text
Generate a new position ordered before/after the supplied Path.
```

Review API documentation for this terminology in a future documentation pass.

---

# 18. Benchmark redesign

Future performance testing should compare LayerKeySort against external baselines instead of primarily comparing different historical LayerKeySort versions.

The historical Stage 8–14 benchmark work remains valuable for regression and memory optimization.

However, it does not answer:

> How competitive is LayerKeySort relative to existing approaches?

Future benchmark categories should include the following.

## Conventional sorting baseline

At minimum:

```text
qsort
stable mergesort implementation
```

Measure:

```text
wall-clock time
comparisons
allocations
peak memory
final memory
```

This comparison is useful mainly to demonstrate the cost of explicit Path/order-maintenance functionality.

LayerKeySort is not expected to beat normal sorting on one-shot array sorting.

---

## Order-key baseline

Compare Path generation against at least one established variable-length indexing approach.

Potential comparison:

```text
fractional indexing
```

Measure:

```text
key length
average key length
maximum key length
insert time
append time
middle-insert time
memory
relabel frequency, if applicable
```

---

# 19. Add pathological benchmark distributions

Required distributions for future benchmarks:

```text
Random unique
Random duplicate
Heavy duplicate
All equal
Ascending
Descending
Nearly sorted
Alternating low/high
Organ-pipe
Repeated insertion before first
Repeated insertion after last
Repeated insertion into same gap
```

Suggested dataset sizes:

```text
N = 1,000
N = 10,000
N = 100,000
```

Optional:

```text
N = 1,000,000
```

only after smaller tests are stable.

---

# 20. Expand structural instrumentation

Future benchmark output should expose more than comparator count.

Possible counters:

```text
ItemComparatorCalls
PathCompareCalls
PathStepsCompared
PathCloneCalls
PathStepsCopied
PathAllocations
PathReallocations
TreePrefixLookups
TreeLevelsVisited
ChildBinarySearches
ChildPointerMoves
ChildMemmoveBytes
TreeNodeAllocations
MergePathGenerations
```

Also report:

```text
AveragePathDepth
MedianPathDepth
P95PathDepth
P99PathDepth
MaximumPathDepth

AveragePathTextLength
MaximumPathTextLength

AverageTreeDepth
MaximumTreeDepth
RootChildCount
Branching distribution
```

This will make algorithmic regressions much easier to diagnose.

---

# 21. Formal complexity documentation

A future release should include a document such as:

```text
docs/COMPLEXITY.md
```

It should describe complexity separately for:

```text
Path compare
Path before
Path after
Path between

Tree explicit insert
Tree item insert
Tree locate

Group build
Group merge

Batch build
Batch merge
```

Each should distinguish:

```text
best case
typical/expected case
worst case
```

and explicitly state assumptions about Path depth and Tree shape.

Avoid publishing a simple `O(n log n)` label unless it is actually justified by the implementation.

---

# 22. Cross-platform validation

The public API is C17, but current official validation is primarily:

```text
MSVC
Windows
x64
```

Future portability work should add:

```text
GCC
Clang
MSVC

Windows
Linux

Debug
Release
ASan
UBSan where supported
```

Potential CI matrix:

```text
windows-latest / MSVC
ubuntu-latest / GCC
ubuntu-latest / Clang
```

---

# 23. Add CMake

Current Visual Studio project files are useful, but a reusable C library should not require consumers to manually reconstruct the build.

Future project structure could add:

```text
CMakeLists.txt
```

with targets such as:

```text
layerkeysort
layerkeysort_tests
layerkeysort_demo
layerkeysort_bench
```

Possible options:

```text
LKS_BUILD_TESTS
LKS_BUILD_BENCHMARKS
LKS_ENABLE_ASAN
```

Keep the Visual Studio project if useful, but CMake would substantially improve portability.

---

# 24. Public allocator support

Current internal allocator instrumentation is strong, but the public library always controls its own allocation strategy.

For general systems use, consider a public allocator interface.

Example conceptual design:

```c
typedef struct LksAllocator {
    void *(*malloc_fn)(size_t size, void *context);
    void *(*realloc_fn)(void *ptr, size_t size, void *context);
    void (*free_fn)(void *ptr, void *context);
    void *context;
} LksAllocator;
```

Potential benefits:

- arenas;
- embedded systems;
- custom memory tracking;
- deterministic allocation;
- test fault injection;
- application-specific memory pools.

This should not be added until ownership semantics are carefully designed.

---

# 25. Embedded-system suitability

LayerKeySort is currently **not** suitable to claim as a bounded-memory MCU / real-time library.

Current design relies heavily on:

```text
malloc
realloc
free
variable-length Paths
dynamic Tree nodes
dynamic child blocks
merge scratch allocation
recursive traversal
```

Missing real-time / embedded guarantees include:

```text
fixed memory ceiling
bounded Path depth
bounded operation latency
caller-provided static storage
no-heap mode
deterministic allocator
WCET analysis
```

If embedded support becomes a future goal, it should probably be a separate design phase rather than a minor port.

Potential future modes:

```text
Desktop/general dynamic mode
Embedded fixed-capacity mode
```

But this is not currently required.

---

# 26. Serialization and parsing

Current Path formatting is one-way.

Future API possibilities:

```c
lks_path_parse(...)
lks_path_serialize(...)
lks_path_deserialize(...)
```

Questions to resolve first:

- Is text format stable across versions?
- Is binary format part of the public ABI?
- Are Paths intended to be persisted?
- Can future Path encoding changes remain compatible?

Do not freeze serialization format until Path semantics are stable.

---

# 27. Deletion / movement / mutation

Current ordering functionality is primarily construction and merging.

A more complete order-maintenance library may eventually need:

```text
delete item
move item before another item
move item after another item
insert between two nodes
replace item
relabel region
rebalance Paths
```

These operations should only be designed after the Path-growth problem is resolved.

---

# 28. Thread safety

Current mutable objects are not guaranteed thread-safe.

That is acceptable.

Future documentation should continue to distinguish between:

```text
independent objects used by separate threads
```

and:

```text
shared mutable Tree / Group objects
```

A general-purpose synchronization layer is probably unnecessary for the core library.

External synchronization is likely sufficient.

---

# 29. Existing testing infrastructure to preserve

The current test system already contains valuable engineering work.

Do not remove it during future refactoring.

Important coverage includes:

```text
deterministic property tests
stable oracle comparisons
duplicate datasets
heavy duplicate datasets
all-equal datasets
sorted datasets
reverse datasets
Path ordering checks
Path uniqueness checks
Path comparator antisymmetry
Path comparator transitivity
before/after/between checks
Tree profile invariants
OOM failure injection
allocation accounting
leak checks
public API smoke tests
AddressSanitizer validation
frozen memory regressions
```

Any algorithmic redesign should reuse these tests where semantics remain applicable.

---

# 30. Additional tests to add immediately when work resumes

Before large refactoring, first add targeted regression tests for known weaknesses.

Checklist:

- [ ] `lks_path_between(negative, positive)` contract test
- [ ] ascending `Group` build with large N
- [ ] descending `Group` build with large N
- [ ] all-equal `Group` build with large N
- [ ] repeated `lks_path_after()` depth-growth test
- [ ] repeated `lks_path_before()` structure-growth test
- [ ] repeated insert into the same gap
- [ ] Path-depth distribution test
- [ ] Path-text-length distribution test
- [ ] child `memmove` instrumentation
- [ ] Path-work instrumentation
- [ ] compare results with a stable reference sort

Add the tests before changing the implementation so the current behavior is measurable.

---

# 31. Potential redesign sequence

When development resumes, avoid changing everything simultaneously.

Suggested sequence:

## Phase 1 — Measure current behavior

- [ ] Add pathological benchmarks
- [ ] Add Path-operation counters
- [ ] Record current memory/runtime/depth results
- [ ] Freeze reproducible baselines

---

## Phase 2 — Fix contract/documentation issues

- [ ] Resolve negative → positive `lks_path_between`
- [ ] Clarify before/after wording
- [ ] Clarify Path persistence semantics
- [ ] Document current worst-case behavior

---

## Phase 3 — Improve endpoint Path allocation

- [ ] Design sparse same-level append/prepend allocation
- [ ] Preserve Path comparison semantics
- [ ] Preserve stable ordering
- [ ] Measure Path-depth improvement
- [ ] Measure memory improvement
- [ ] Measure runtime improvement

This should be the first major algorithm change.

---

## Phase 4 — Improve gap allocation

- [ ] Study fractional indexing/order-maintenance literature
- [ ] Design better between-position allocation
- [ ] Test repeated insertion into identical/narrow gaps
- [ ] Decide whether relabeling is allowed

---

## Phase 5 — Investigate Tree/Path decoupling

- [ ] Measure cost of current prefix Tree topology
- [ ] Prototype independent balanced index
- [ ] Compare memory
- [ ] Compare lookup
- [ ] Compare insertion
- [ ] Evaluate compatibility impact

Only proceed if measurement shows meaningful benefit.

---

## Phase 6 — Portability

- [ ] CMake
- [ ] GCC
- [ ] Clang
- [ ] Linux
- [ ] CI
- [ ] UBSan

---

## Phase 7 — Additional public API

Only after algorithm semantics stabilize:

- [ ] custom allocator
- [ ] Path parser
- [ ] serialization
- [ ] deletion
- [ ] move operations
- [ ] relabel/rebalance API if necessary

---

# 32. What should NOT be prioritized when development resumes

Avoid spending another large optimization cycle only reducing a few bytes from structure layouts before addressing Path growth.

Past work already optimized:

```text
Path representation
Tree nodes
Tree child storage
merge lifetime
peak memory
allocation behavior
```

Those optimizations are useful and should remain.

However, the highest-value next work is architectural:

```text
control Path depth
control Path growth
control worst-case behavior
```

Saving another small constant number of bytes per node is less important than preventing a Path from growing linearly with insertion count.

---

# 33. Project messaging

Recommended wording:

> LayerKeySort is a stable C17 ordering library that assigns hierarchical Path positions to ordered items and supports independently built Groups and stable merging.

Avoid strong claims such as:

```text
faster than quicksort
better than mergesort
new universal sorting algorithm
O(n log n) sorting algorithm
memory-efficient for all distributions
ideal for embedded systems
```

unless future benchmarks and formal analysis support them.

The project's value does not require those claims.

---

# 34. Long-term project identity

There are two possible directions.

## Direction A — Sorting library

Focus on:

```text
raw sorting throughput
comparison count
low memory
competition with qsort/mergesort
```

This would require substantial redesign and would place LayerKeySort against highly optimized mature algorithms.

This is probably not the strongest unique direction.

---

## Direction B — Explicit ordering / order-maintenance library

Focus on:

```text
stable ordering
explicit Path coordinates
insertion between positions
group-local ordering
stable group merging
persistent/inspectable order representation
```

This direction better matches the existing design.

If development continues, this is currently the more natural identity.

---

# 35. Definition of success for the next major version

A future algorithm-focused release should ideally demonstrate all of the following:

- [ ] ascending input no longer produces near-linear Path depth;
- [ ] all-equal large datasets remain manageable;
- [ ] repeated append/prepend has controlled Path growth;
- [ ] repeated insertion into the same gap has a documented strategy;
- [ ] worst-case behavior is documented honestly;
- [ ] Path comparator remains a valid total order;
- [ ] stable ordering remains correct;
- [ ] Group merge stability remains correct;
- [ ] OOM guarantees remain correct;
- [ ] no memory leaks;
- [ ] random `N=10000` regressions remain correct;
- [ ] pathological datasets are included in permanent regression testing;
- [ ] external baselines are included in performance evaluation;
- [ ] GCC/Clang builds are validated;
- [ ] CI runs automatically.

---

# 36. Resume point

When returning to LayerKeySort after the pause, **do not begin by modifying production code**.

Start with:

```text
1. Re-read this issue.
2. Re-run current v1.0.0 validation.
3. Add pathological benchmarks.
4. Record current Path depth / memory / runtime behavior.
5. Add the negative→positive between regression test.
6. Design a replacement endpoint Path allocator on paper.
7. Only then modify path allocation.
```

The first design question to answer should be:

> How can sequential append/prepend generate bounded-growth Paths while preserving the current LayerKeySort ordering semantics?

A likely first experiment is replacing:

```text
A0
A0/A0
A0/A0/A0
...
```

with a sparse same-level sequence before deeper levels are required.

That is currently the most important unfinished algorithmic problem in LayerKeySort.

---

## Final note

v1.0.0 does not need to be treated as a failed design because these limitations exist.

It already provides:

- a coherent public API;
- explicit Path semantics;
- stable ordering;
- stable Group merging;
- extensive property testing;
- allocation-failure validation;
- memory instrumentation;
- AddressSanitizer validation;
- documentation;
- examples;
- visualization;
- a reproducible baseline for future research.

The next stage should therefore be treated as **algorithmic evolution**, not a rewrite motivated by failure.

For now, development is intentionally paused.

Deferred Algorithmic Improvements and Technical Debt #1

Description

Deferred Algorithmic Improvements and Technical Debt

Status

1. Current project positioning

2. Important design strength to preserve

2.1 Stable ordering

2.2 Stable Group merging

2.3 Explicit Path positions

2.4 Caller-owned items

2.5 Failure behavior

3. Main algorithmic issue: uncontrolled Path growth

3.1 Sequential append behavior

4. Existing benchmark evidence of the Path-growth problem

5. Comparator count is not sufficient for performance analysis

6. Potential severe worst-case time complexity

7. Reverse-order degeneration is different

8. All-equal data is especially important

9. Random-data scalability is much better and should remain part of the comparison

10. Highest-priority future algorithm work: redesign endpoint Path allocation

11. Consider wider-gap allocation

12. Research references / concepts for future work

13. Consider separating Path representation from Tree topology

14. Consider Path depth limits and relabeling

15. Clarify whether Path identity is persistent or ephemeral

16. Possible API contract issue: negative-to-positive lks_path_between

Option A — implementation bug

Option B — intentional restriction

17. API wording issue: "immediately before / after"

18. Benchmark redesign

Conventional sorting baseline

Order-key baseline

19. Add pathological benchmark distributions

20. Expand structural instrumentation

21. Formal complexity documentation

22. Cross-platform validation

23. Add CMake

24. Public allocator support

25. Embedded-system suitability

26. Serialization and parsing

27. Deletion / movement / mutation

28. Thread safety

29. Existing testing infrastructure to preserve

30. Additional tests to add immediately when work resumes

31. Potential redesign sequence

Phase 1 — Measure current behavior

Phase 2 — Fix contract/documentation issues

Phase 3 — Improve endpoint Path allocation

Phase 4 — Improve gap allocation

Phase 5 — Investigate Tree/Path decoupling

Phase 6 — Portability

Phase 7 — Additional public API

32. What should NOT be prioritized when development resumes

33. Project messaging

34. Long-term project identity

Direction A — Sorting library

Direction B — Explicit ordering / order-maintenance library

35. Definition of success for the next major version

36. Resume point

Final note

Activity

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

16. Possible API contract issue: negative-to-positive `lks_path_between`