using System;
class Program
{
/// <summary>
/// Sorts a span of elements in-place in non-decreasing order using Gnome Sort.
/// </summary>
/// <typeparam name="T">Type of elements, constrained to types implementing IComparable.</typeparam>
/// <param name="data">The span of elements to be sorted in place.</param>
/// <remarks>
/// Algorithm Logic (Single Loop):
/// - Advances through the collection using a single while loop index.
/// - Moves forward when adjacent elements are in correct relative order.
/// - When an out-of-order adjacent pair is encountered, swaps the elements
/// and steps backward one index to verify order against preceding items.
/// - Time Complexity: O(N) best case (already sorted), O(N^2) worst case.
/// - Space Complexity: O(1) auxiliary space.
/// </remarks>
public static void SingleLoopSort<T>(Span<T> data) where T : IComparable<T>
{
int pos = 0;
int len = data.Length;
while (pos < len)
{
// Advance if at index 0 or if adjacent pair is in correct order
if (pos == 0 || data[pos].CompareTo(data[pos - 1]) >= 0) {
pos++;
}
else
{
// Swap adjacent out-of-order elements using tuple deconstruction
(data[pos], data[pos - 1]) = (data[pos - 1], data[pos]);
pos--;
}
}
}
static void Main()
{
int[] numbers = { 42, -5, 12, 0, 89, -18, 33, 7 };
Console.WriteLine("Original array:");
Console.WriteLine(string.Join(" ", numbers));
// Memory/Span overload operates directly on array memory without extra allocations
SingleLoopSort(numbers.AsSpan());
Console.WriteLine("\nSorted array:");
Console.WriteLine(string.Join(" ", numbers));
}
}
/*
run:
Original array:
42 -5 12 0 89 -18 33 7
Sorted array:
-18 -5 0 7 12 33 42 89
*/
