Property-Based Testing for a Simple Sorting Algorithm in Rust

This challenge focuses on implementing and testing a basic sorting function using property-based testing in Rust. Property-based testing is a powerful technique that verifies your code by generating many random inputs and checking if certain "properties" (invariants or expected behaviors) hold true for all of them. This helps uncover edge cases and bugs that might be missed with traditional example-based testing.

Problem Description

Your task is to implement a simple sorting function in Rust and then write property-based tests for it using the proptest crate.

You need to:

1. Implement a sorting function: Create a function named my_sort that takes a mutable slice of integers (&mut [i32]) and sorts it in ascending order in-place. For simplicity, you can use any sorting algorithm you are familiar with (e.g., bubble sort, insertion sort). The focus is on the testing, not on the efficiency of the sort itself.
2. Define test properties: Identify and implement properties that a correctly sorted list should satisfy. These properties will be checked by proptest.
3. Write property-based tests: Use proptest to generate random input slices and assert that your my_sort function adheres to the defined properties.

Key requirements:

• The my_sort function must sort the slice in ascending order.
• The sorting must happen in-place (modify the original slice).
• Property-based tests must be written using the proptest crate.
• The tests should cover various scenarios, including empty slices, single-element slices, already sorted slices, reverse-sorted slices, and slices with duplicate elements.

Expected behavior:

Your my_sort function should correctly sort any given &mut [i32] slice. Your property-based tests should pass for a correctly implemented sorting function and fail (or report errors) for incorrect implementations.

Examples

Example 1: Basic Sorting

Input to my_sort: &mut [3, 1, 4, 1, 5, 9, 2, 6] Output after my_sort: &mut [1, 1, 2, 3, 4, 5, 6, 9] Explanation: The slice is sorted in ascending order.

Example 2: Empty Slice

Input to my_sort: &mut [] Output after my_sort: &mut [] Explanation: An empty slice remains empty and is considered sorted.

Example 3: Slice with Duplicates

Input to my_sort: &mut [5, 2, 8, 2, 5, 5] Output after my_sort: &mut [2, 2, 5, 5, 5, 8] Explanation: The sorting algorithm correctly handles duplicate values, preserving their count and relative order within the sorted sequence.

Constraints

• The input to my_sort will be a mutable slice of i32 integers.
• The size of the input slices generated by proptest can vary, but proptest has default limits for collection sizes that are generally sufficient. You don't need to explicitly set these limits unless you encounter specific issues.
• The values of the i32 integers will be within the standard range for i32.

Notes

• To use proptest, you'll need to add it as a development dependency in your Cargo.toml file.
• Think about the fundamental properties of a sorted list. For example:
  • Every element is less than or equal to the element that follows it.
  • The smallest element in the original list should be the first element, and the largest should be the last.
  • The number of elements in the sorted list should be the same as the original list.
  • The multiset of elements in the original list should be the same as the multiset of elements in the sorted list (i.e., no elements are added or lost, and duplicates are preserved).
• You can use Rust's standard library sorting (slice::sort) as a reference to verify your sorting function's correctness within your property tests. This is a common and effective pattern in property-based testing: generate an input, run your (potentially buggy) implementation, run a known-correct implementation, and assert that their outputs are identical or that your implementation satisfies certain invariants that the known-correct one also satisfies.