merge_inplace()

template<typename Iterator, typename Compare>

void fl::detail::merge_inplace	(	Iterator	first,
		Iterator	middle,
		Iterator	last,
		Compare	comp )

Definition at line 399 of file algorithm.h.

                                                                                 {
    // If one of the ranges is empty, nothing to merge
    if (first == middle || middle == last) {
        return;
    }
    
    // If arrays are small enough, use insertion-based merge
    auto left_size = middle - first;
    auto right_size = last - middle;
    if (left_size + right_size <= 32) {
        // Simple insertion-based merge for small arrays
        Iterator left = first;
        Iterator right = middle;
        
        while (left < middle && right < last) {
            if (!comp(*right, *left)) {
                // left element is in correct position
                ++left;
            } else {
                // right element needs to be inserted into left part
                auto value = fl::move(*right);
                Iterator shift_end = right;
                Iterator shift_start = left;
                
                // Shift elements to make room
                while (shift_end > shift_start) {
                    *shift_end = fl::move(*(shift_end - 1));
                    --shift_end;
                }
                
                *left = fl::move(value);
                ++left;
                ++middle;  // middle has shifted right
                ++right;
            }
        }
        return;
    }
    
    // For larger arrays, use rotation-based merge
    if (left_size == 0 || right_size == 0) {
        return;
    }
    
    if (left_size == 1) {
        // Find insertion point for the single left element in right array
        Iterator pos = lower_bound_impl(middle, last, *first, comp);
        rotate_impl(first, middle, pos);
        return;
    }
    
    if (right_size == 1) {
        // Find insertion point for the single right element in left array  
        Iterator pos = lower_bound_impl(first, middle, *(last - 1), comp);
        rotate_impl(pos, middle, last);
        return;
    }
    
    // Divide both arrays and recursively merge
    Iterator left_mid = first + left_size / 2;
    Iterator right_mid = lower_bound_impl(middle, last, *left_mid, comp);
    
    // Rotate to bring the two middle parts together
    rotate_impl(left_mid, middle, right_mid);
    
    // Update middle position
    Iterator new_middle = left_mid + (right_mid - middle);
    
    // Recursively merge the two parts
    merge_inplace(first, left_mid, new_middle, comp);
    merge_inplace(new_middle, right_mid, last, comp);
}

References lower_bound_impl(), merge_inplace(), fl::move(), pos, and rotate_impl().

Referenced by merge_inplace(), and mergesort_impl().

Here is the call graph for this function:

Here is the caller graph for this function: