| 457 | // In-place merge operation for merge sort (stable sort) |
| 458 | template <typename Iterator, typename Compare> |
| 459 | void merge_inplace(Iterator first, Iterator middle, Iterator last, Compare comp) FL_NOEXCEPT { |
| 460 | // If one of the ranges is empty, nothing to merge |
| 461 | if (first == middle || middle == last) { |
| 462 | return; |
| 463 | } |
| 464 | |
| 465 | // If arrays are small enough, use insertion-based merge |
| 466 | auto left_size = middle - first; |
| 467 | auto right_size = last - middle; |
| 468 | if (left_size + right_size <= 32) { |
| 469 | // Simple insertion-based merge for small arrays |
| 470 | Iterator left = first; |
| 471 | Iterator right = middle; |
| 472 | |
| 473 | while (left < middle && right < last) { |
| 474 | if (!comp(*right, *left)) { |
| 475 | // left element is in correct position |
| 476 | ++left; |
| 477 | } else { |
| 478 | // right element needs to be inserted into left part |
| 479 | auto value = fl::move(*right); |
| 480 | Iterator shift_end = right; |
| 481 | Iterator shift_start = left; |
| 482 | |
| 483 | // Shift elements to make room |
| 484 | while (shift_end > shift_start) { |
| 485 | *shift_end = fl::move(*(shift_end - 1)); |
| 486 | --shift_end; |
| 487 | } |
| 488 | |
| 489 | *left = fl::move(value); |
| 490 | ++left; |
| 491 | ++middle; // middle has shifted right |
| 492 | ++right; |
| 493 | } |
| 494 | } |
| 495 | return; |
| 496 | } |
| 497 | |
| 498 | // For larger arrays, use rotation-based merge |
| 499 | if (left_size == 0 || right_size == 0) { |
| 500 | return; |
| 501 | } |
| 502 | |
| 503 | if (left_size == 1) { |
| 504 | // Find insertion point for the single left element in right array |
| 505 | Iterator pos = lower_bound_impl(middle, last, *first, comp); |
| 506 | rotate_impl(first, middle, pos); |
| 507 | return; |
| 508 | } |
| 509 | |
| 510 | if (right_size == 1) { |
| 511 | // Find insertion point for the single right element in left array |
| 512 | Iterator pos = lower_bound_impl(first, middle, *(last - 1), comp); |
| 513 | rotate_impl(pos, middle, last); |
| 514 | return; |
| 515 | } |
| 516 |
no test coverage detected