Bubble sort C++, space complexity O(n)

bubble_sort.cpp

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

/*
O(n^2) in avg and worst.
Can be done easily at space complexity O(n).
*/

// Implementation
std::vector<int> sort(std::vector<int>& array) {
    int sz = array.size() - 1;
    bool sorted;
    int j = 0; // the largest element will always be put to the back
    while(true) {
        sorted = true;
        for(int i = 0; i < sz - j; i++) {
            if (array[i] > array[i+1]) {
                std::swap(array[i], array[i+1]);
                sorted = false;
            }
        }
        j+=1;
        if (sorted) break;
    }
    return array;
}

// Tests

void test_empty_array() {
    std::vector<int> empty;
    empty = sort(empty);
    assert(empty.empty() && "Test with empty array failed");
}

void test_single_element() {
    std::vector<int> single = {1};
    single = sort(single);
    assert(single[0] == 1 && "Test with single element failed");
}

void test_sorted_array() {
    std::vector<int> sorted = {1, 2, 3, 4, 5};
    sorted = sort(sorted);
    assert(std::is_sorted(sorted.begin(), sorted.end()) && "Test with sorted array failed");
}

void test_reverse_sorted_array() {
    std::vector<int> reverse_sorted = {5, 4, 3, 2, 1};
    reverse_sorted = sort(reverse_sorted);
    assert(std::is_sorted(reverse_sorted.begin(), reverse_sorted.end()) && "Test with reverse sorted array failed");
}

void test_large_array() {
    std::vector<int> large(1000);
    for (int i = 0; i < 1000; ++i) {
        large[i] = 1000 - i; // Create reverse order
    }
    large = sort(large);
    assert(std::is_sorted(large.begin(), large.end()) && "Test with large array failed");
}

void test_array_with_duplicates() {
    std::vector<int> duplicates = {2, 3, 2, 3, 2};
    duplicates = sort(duplicates);
    assert(std::is_sorted(duplicates.begin(), duplicates.end()) && "Test with array of duplicates failed");
}

void test_all_identical_elements() {
    std::vector<int> identical(10, 5); // 10 elements, all are 5
    identical = sort(identical);
    assert(std::is_sorted(identical.begin(), identical.end()) && "Test with all identical elements failed");
}


// Main
void run_all_tests() {
    test_empty_array();
    test_single_element();
    test_sorted_array();
    test_reverse_sorted_array();
    test_large_array();
    test_array_with_duplicates();
    test_all_identical_elements();
}

int main() {
    run_all_tests();
    std::cout << "All tests passed successfully!\n";
    return 0;
}