Does InsertionSort work as expected?

[shlyakpavel]

https://github.com/LadybirdBrowser/ladybird/blob/dd11d48a1dcc96a77f4e11bd72f558503057e775/AK/InsertionSort.h#L14-L23

Is this code supposed to start at the beginning and end at the end? If so, should not be the inner loop be something like

for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
    swap(col[j], col[j - 1]);

Here's a test that indicated what I'm worried about

TEST_CASE(sorts_subrange_without_affecting_outside_elements)
{
    // Initialize a vector with known values
    Vector<int> ints = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    Vector<int> original_ints = ints;

    // Define the subrange to sort (indices 3 to 6)
    ssize_t start = 3;
    ssize_t end = 6;

    // Sort the subrange in ascending order
    insertion_sort(ints, start, end, [](auto& a, auto& b) { return a < b; });

    // Verify that the subrange is sorted
    for (ssize_t i = start; i < end; ++i) {
        EXPECT(ints[i] <= ints[i + 1]);
    }

    // Check that elements before 'start' remain unchanged
    for (ssize_t i = 0; i < start; ++i) {
        EXPECT_EQ(ints[i], original_ints[i]);
    }

    // Check that elements after 'end' remain unchanged
    for (ssize_t i = end + 1; i < static_cast<ssize_t>(ints.size()); ++i) {
        EXPECT_EQ(ints[i], original_ints[i]);
    }
}

It fails. So either I don't get the idea how it's supposed to work or it's just not working as expected....

[tcl3]

I'm not sure whether the current behavior is intentional or a bug, but our quick_sort implementation seems to behave as your test expects. You can see this if you substitute insertion_sort for dual_pivot_quick_sort in the above test.

I think it would be best if the behavior was consistent across different sorts.

[shlyakpavel]

Deleted. Stupid stuff

[ADKaster]

I think it would be useful to create a test class that measures the number of times an instance is swapped or compared using the comparator.

Doing so would let us validate that while quick_sort behaves the same with either implementation, it does less compares/swaps in one implementation over another.

Or some benchmarks.

Intuitively, the current implementation seems incorrect, but in its current uses that incorrect behavior doesn't seem to affect the correctness of the calling code.

[raikrahul]

I am unable to understand how this is not a bug?