Does InsertionSort work as expected?

[shlyakpavel]

ladybird/AK/InsertionSort.h

Lines 14 to 23 in dd11d48

	// Standard Insertion Sort, with `end` inclusive!
	template<typename Collection, typename Comparator, typename T = decltype(declval<Collection>()[declval<int>()])>
	void insertion_sort(Collection& col, ssize_t start, ssize_t end, Comparator comparator)
	requires(Indexable<Collection, T>)
	{
	for (ssize_t i = start + 1; i <= end; ++i) {
	for (ssize_t j = i; j > 0 && comparator(col[j], col[j - 1]); --j)
	swap(col[j], col[j - 1]);
	}
	}

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?

[shlyakpavel]

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

This is not a bug as long as nothing depends on the affected behavior. There's a high chance it's a bug in serenity, where more parts of the system depend on that code, whereas the only place we use it in Ladybird is quicksort, and that doesn't depend on this function actually not writing outside of the provided bounds.

However, I believe that code is bug-prone and it might affect something one day when someone uses it outside of quicksort