Runtime: Array objects should be able to represent their internal state of being sorted

[NonSecwitter]

Rationale

The condition of being sorted is a question of the internal state of the array. Without an internal representation to convey it's state, knowing the internal state of being sorted depends on (a) compliance with requirements known by successful communication through documentation or (b) implementing the routine to always perform a sort operation on a received array.

The first case pushes the responsibility of creating and maintaining knowledge of internal state onto the client. The second case would likely be grossly inefficient, and requires the client to know the internal behavior of providing sort functionality. In both cases, this is a violation of data abstraction principals and makes the implementation of the provided function dependent on the client for correct operation.

Adding a property IsSorted helps relieve the amiguity, giving libraries the opportunity to check for the state of being sorted, to sort when needed, and to not sort when not needed.

Usage

A lot of operations involving arrays are dependent on its state of being sorted or unsorted. Because the Array object does not indicate it's own internal state, it creates ambiguity

A simple example of how this could be beneficial:

public int BinarySearch(Array HayStack, object Needle)
{
    if(!HayStack.IsSorted)
        HayStack.Sort();

    BinarySearchFunctionality();
}

Proposed API

public abstract partial class Array : System.Collections.ICollection, System.Collections.IEnumerable, System.Collections.IList, System.Collections.IStructuralComparable, System.Collections.IStructuralEquatable, System.ICloneable
    {
        internal Array() { }
        public bool IsFixedSize { get { throw null; } }
        public bool IsReadOnly { get { throw null; } }
        public bool IsSynchronized { get { throw null; } }


// New interface...
        public bool IsSorted { get { throw null; } }
// End new interface


        public int Length { get { throw null; } }
        public long LongLength { get { throw null; } }
        public int Rank { get { throw null; } }
        public object SyncRoot { get { throw null; } }
        int System.Collections.ICollection.Count { get { throw null; } }
        object System.Collections.IList.this[int index] { get { throw null; } set { } }
        public static System.Collections.ObjectModel.ReadOnlyCollection<T> AsReadOnly<T>(T[] array) { throw null; }
        public static int BinarySearch(System.Array array, int index, int length, object value) { throw null; }
        public static int BinarySearch(System.Array array, int index, int length, object value, System.Collections.IComparer comparer) { throw null; }
        public static int BinarySearch(System.Array array, object value) { throw null; }
        public static int BinarySearch(System.Array array, object value, System.Collections.IComparer comparer) { throw null; }
        public static int BinarySearch<T>(T[] array, int index, int length, T value) { throw null; }
        public static int BinarySearch<T>(T[] array, int index, int length, T value, System.Collections.Generic.IComparer<T> comparer) { throw null; }
        public static int BinarySearch<T>(T[] array, T value) { throw null; }
        public static int BinarySearch<T>(T[] array, T value, System.Collections.Generic.IComparer<T> comparer) { throw null; }
        public static void Clear(System.Array array, int index, int length) { }
        public object Clone() { throw null; }
        public static void ConstrainedCopy(System.Array sourceArray, int sourceIndex, System.Array destinationArray, int destinationIndex, int length) { }
        public static TOutput[] ConvertAll<TInput, TOutput>(TInput[] array, System.Converter<TInput, TOutput> converter) { throw null; }
        public static void Copy(System.Array sourceArray, System.Array destinationArray, int length) { }
        public static void Copy(System.Array sourceArray, System.Array destinationArray, long length) { }
        public static void Copy(System.Array sourceArray, int sourceIndex, System.Array destinationArray, int destinationIndex, int length) { }
        public static void Copy(System.Array sourceArray, long sourceIndex, System.Array destinationArray, long destinationIndex, long length) { }
        public void CopyTo(System.Array array, int index) { }
        public void CopyTo(System.Array array, long index) { }
        public static System.Array CreateInstance(System.Type elementType, int length) { throw null; }
        public static System.Array CreateInstance(System.Type elementType, int length1, int length2) { throw null; }
        public static System.Array CreateInstance(System.Type elementType, int length1, int length2, int length3) { throw null; }
        public static System.Array CreateInstance(System.Type elementType, params int[] lengths) { throw null; }
        public static System.Array CreateInstance(System.Type elementType, int[] lengths, int[] lowerBounds) { throw null; }
        public static System.Array CreateInstance(System.Type elementType, params long[] lengths) { throw null; }
        public static T[] Empty<T>() { throw null; }
        public static bool Exists<T>(T[] array, System.Predicate<T> match) { throw null; }
        public static void Fill<T>(T[] array, T value) { }
        public static void Fill<T>(T[] array, T value, int startIndex, int count) { }
        public static T[] FindAll<T>(T[] array, System.Predicate<T> match) { throw null; }
        public static int FindIndex<T>(T[] array, int startIndex, int count, System.Predicate<T> match) { throw null; }
        public static int FindIndex<T>(T[] array, int startIndex, System.Predicate<T> match) { throw null; }
        public static int FindIndex<T>(T[] array, System.Predicate<T> match) { throw null; }
        public static int FindLastIndex<T>(T[] array, int startIndex, int count, System.Predicate<T> match) { throw null; }
        public static int FindLastIndex<T>(T[] array, int startIndex, System.Predicate<T> match) { throw null; }
        public static int FindLastIndex<T>(T[] array, System.Predicate<T> match) { throw null; }
        public static T FindLast<T>(T[] array, System.Predicate<T> match) { throw null; }
        public static T Find<T>(T[] array, System.Predicate<T> match) { throw null; }
        public static void ForEach<T>(T[] array, System.Action<T> action) { }
        public System.Collections.IEnumerator GetEnumerator() { throw null; }
        public int GetLength(int dimension) { throw null; }
        public long GetLongLength(int dimension) { throw null; }
        public int GetLowerBound(int dimension) { throw null; }
        public int GetUpperBound(int dimension) { throw null; }
        public object GetValue(int index) { throw null; }
        public object GetValue(int index1, int index2) { throw null; }
        public object GetValue(int index1, int index2, int index3) { throw null; }
        public object GetValue(params int[] indices) { throw null; }
        public object GetValue(long index) { throw null; }
        public object GetValue(long index1, long index2) { throw null; }
        public object GetValue(long index1, long index2, long index3) { throw null; }
        public object GetValue(params long[] indices) { throw null; }
        public static int IndexOf(System.Array array, object value) { throw null; }
        public static int IndexOf(System.Array array, object value, int startIndex) { throw null; }
        public static int IndexOf(System.Array array, object value, int startIndex, int count) { throw null; }
        public static int IndexOf<T>(T[] array, T value) { throw null; }
        public static int IndexOf<T>(T[] array, T value, int startIndex) { throw null; }
        public static int IndexOf<T>(T[] array, T value, int startIndex, int count) { throw null; }
        public void Initialize() { }
        public static int LastIndexOf(System.Array array, object value) { throw null; }
        public static int LastIndexOf(System.Array array, object value, int startIndex) { throw null; }
        public static int LastIndexOf(System.Array array, object value, int startIndex, int count) { throw null; }
        public static int LastIndexOf<T>(T[] array, T value) { throw null; }
        public static int LastIndexOf<T>(T[] array, T value, int startIndex) { throw null; }
        public static int LastIndexOf<T>(T[] array, T value, int startIndex, int count) { throw null; }
        public static void Resize<T>(ref T[] array, int newSize) { }
        public static void Reverse(System.Array array) { }
        public static void Reverse(System.Array array, int index, int length) { }
        public static void Reverse<T>(T[] array) { }
        public static void Reverse<T>(T[] array, int index, int length) { }
        public void SetValue(object value, int index) { }
        public void SetValue(object value, int index1, int index2) { }
        public void SetValue(object value, int index1, int index2, int index3) { }
        public void SetValue(object value, params int[] indices) { }
        public void SetValue(object value, long index) { }
        public void SetValue(object value, long index1, long index2) { }
        public void SetValue(object value, long index1, long index2, long index3) { }
        public void SetValue(object value, params long[] indices) { }
        public static void Sort(System.Array array) { }
        public static void Sort(System.Array keys, System.Array items) { }
        public static void Sort(System.Array keys, System.Array items, System.Collections.IComparer comparer) { }
        public static void Sort(System.Array keys, System.Array items, int index, int length) { }
        public static void Sort(System.Array keys, System.Array items, int index, int length, System.Collections.IComparer comparer) { }
        public static void Sort(System.Array array, System.Collections.IComparer comparer) { }
        public static void Sort(System.Array array, int index, int length) { }
        public static void Sort(System.Array array, int index, int length, System.Collections.IComparer comparer) { }
        public static void Sort<T>(T[] array) { }
        public static void Sort<T>(T[] array, System.Collections.Generic.IComparer<T> comparer) { }
        public static void Sort<T>(T[] array, System.Comparison<T> comparison) { }
        public static void Sort<T>(T[] array, int index, int length) { }
        public static void Sort<T>(T[] array, int index, int length, System.Collections.Generic.IComparer<T> comparer) { }
        public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items) { }
        public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, System.Collections.Generic.IComparer<TKey> comparer) { }
        public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length) { }
        public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length, System.Collections.Generic.IComparer<TKey> comparer) { }
        int System.Collections.IList.Add(object value) { throw null; }
        void System.Collections.IList.Clear() { }
        bool System.Collections.IList.Contains(object value) { throw null; }
        int System.Collections.IList.IndexOf(object value) { throw null; }
        void System.Collections.IList.Insert(int index, object value) { }
        void System.Collections.IList.Remove(object value) { }
        void System.Collections.IList.RemoveAt(int index) { }
        int System.Collections.IStructuralComparable.CompareTo(object other, System.Collections.IComparer comparer) { throw null; }
        bool System.Collections.IStructuralEquatable.Equals(object other, System.Collections.IEqualityComparer comparer) { throw null; }
        int System.Collections.IStructuralEquatable.GetHashCode(System.Collections.IEqualityComparer comparer) { throw null; }
        public static bool TrueForAll<T>(T[] array, System.Predicate<T> match) { throw null; }
    }

Details

The Sort operation will need to update the internal flag indicating current sort state.

Open Questions

• Handling scenarios where the condition of being ordered may change:
  
  
  
  • When inserting items, the client can do insertion sort or just add elements in whatever order. Only allowing the Array object itself to manage the internal state may require adding methods for SortedInsert
  
  

[stephentoub]

Adding a property IsSorted helps relieve the amiguity, giving libraries the opportunity to check for the state of being sorted, to sort when needed, and to not sort when not needed.

Where do you expect this data to be stored?

What happens if the sorting is done by something other than Array.Sort? What happens if the data was created from the beginning already in sorted order?

How does this deal with the fact that there are an infinite number of sortings, based on the comparer used?

What happens when the array is modified (e.g. swapping two elements) such that it's no longer sorted?

Etc.

[NonSecwitter]

Adding a property IsSorted helps relieve the amiguity, giving libraries the opportunity to check for the state of being sorted, to sort when needed, and to not sort when not needed.

Where do you expect this data to be stored?

A private boolean should be sufficient

What happens if the sorting is done by something other than Array.Sort?

Complete data encapsulation should isolate the underlying Array from manipulation except through provided function interfaces, including the [ ] operator, enabling the Array to maintain the status of its own internal state.

What happens if the data was created from the beginning already in sorted order?

Perhaps this could be a constructor overload? new Array(Objects[] HayStack, bool Sorted) and Clone() operations could copy the IsSorted state.

How does this deal with the fact that there are an infinite number of sortings, based on the comparer used?

IsSorted should be false by default, and should only change if an instance method that performs a sort has been successfully completed, or if it was created with the overloaded constructor.

What happens when the array is modified (e.g. swapping two elements) such that it's no longer sorted?

An additional interface function InsertSorted() could be added to place the new item based on the comparer's logic, which will leave IsSorted as true. Any other insert operation, including assignments like HayStack[i] = x; should change IsSorted to false.

Etc.

If we're completely abstracting the array, then we shouldn't be able to operate on it except for through provided interfaces, so maybe this will require a bit more adjustment than adding a single property, but it seems doable, and like a property that could improve design and reduce opportunities for bugs.

[Gnbrkm41]

Perhaps this could be a constructor overload? new Array(Objects[] HayStack, bool Sorted) and Clone() operations could copy the IsSorted state.

What happens if the consumer decides to lie to the constructor? e.g. new Array(HayStack, true) when HayStack is not sorted.

Wouldn't the field be unnecessary if the objects stored in the array cannot be ordered? (i.e. types that do not implement IComparable)

[stephentoub]

Complete data encapsulation should isolate the underlying Array from manipulation except through provided function interfaces, including the [ ] operator, enabling the Array to maintain the status of its own internal state.

This is not how arrays in .NET work.

IsSorted should be false by default, and should only change if an instance method that performs a sort has been successfully completed, or if it was created with the overloaded constructor.

In that case it'll very frequently be wrong and thus unreliable. If I give you an int[] and its IsSorted returns true, what can you possibly do with that information? You don't know what comparer was used to sort it.

If we're completely abstracting the array, then we shouldn't be able to operate on it except for through provided interfaces, so maybe this will require a bit more adjustment than adding a single property, but it seems doable, and like a property that could improve design and reduce opportunities for bugs.

At that point you're talking about adding a whole new Array-like type to .NET. It's way more than just an IsSorted property, which for all the issues I highlighted is problematic.

[NonSecwitter]

This is not how arrays in .NET work.

Array's aren't primitive... so, why not?

IsSorted should be false by default, and should only change if an instance method that performs a sort has been successfully completed, or if it was created with the overloaded constructor.

In that case it'll very frequently be wrong and thus unreliable. If I give you an int[] and its IsSorted returns true, what can you possibly do with that information? You don't know what comparer was used to sort it.

As the person implementing a function, like the BinarySearch, I don't really worry if the comparer someone used is the one that I would have used. All I want to know is if the underlying array is sorted according to their standards before I perform my work. If they sorted it incorrectly and can't produce the correct results, that's outside my scope of responsibility and outside the scope of knowledge that I need to perform my action. How is this different than just receiving an unsorted array where I should have received a sorted array? I can check to see if the attempt was even made before wasting cycles.

As it is, you're already _assuming_ an implicit IsSorted is true to begin with and you _already_ don't know what comparer was used to sort it. The, a bunch of cycles get wasted operating on the array based on nothing more than an assumption that the user followed directions. IsSorted moves the assumption into the realm of explicit state. If the Array carries a comparer with it, then the sort() function can be called at any point based on knowledge that it carries with itself about its own comparer and current sort state. If direcy manipulation of the Array is hidden from the user, then the Array can always accurately maintain its sort state.

As the person passing the Array around, I can improve my use of the array by checking IsSorted when I'm about to use the array, and sorting if and only if IsSorted == false instead of needing to dig back through code and remember if it's been sorted.

What happens if the consumer decides to lie to the constructor? e.g. new Array(HayStack, true) when HayStack is not sorted.

I imagine the same thing that would happen anytime you lie to any function call. It won't work correctly.

[stephentoub]

Array's aren't primitive... so, why not?

I don't know what you mean by that. Anyone given a T[] can write into the array. That is a very well supported operation that maps to IL operations. Augmenting the implementation of those IL operations to also track sorting would be significant overhead, and again, not to mention impossible, since the T[] has no idea of how it was sorted and thus what it means to be sorted and thus what comparison to check as part of the write to determine whether it's still sorted.

All I want to know is if the underlying array is sorted according to their standards before I perform my work. If they sorted it incorrectly and can't produce the correct results, that's outside my scope of responsibility and outside the scope of knowledge that I need to perform my action. How is this different than just receiving an unsorted array where I should have received a sorted array? I can check to see if the attempt was even made before wasting cycles.

The whole purpose of your IsSorted is to be able to avoid doing a sort in cases where sorting is needed (or to fall back to something that doesn't require sorting if it's not sorted). But whether something is or is not sorted has no meaning in and of itself: it needs to know according to what ordering. There's nothing any consumer of IsSorted could do without knowing what it was sorted according to; it would have to assume it's not sorted, which is no different from today.

I appreciate your desire to contribute, and I understand you're trying to make certain things more efficient, but I simply do not understand how this proposal is valuable.

[Gnbrkm41]

I imagine the same thing that would happen anytime you lie to any function call. It won't work correctly.

if IsSorted cannot guarantee that the array has/has not been sorted I would think that it would barely change anything. Wouldn't it be the same as manually keeping track of whether the array has been sorted or not? It wouldn't add any significant value by adding it.

[NonSecwitter]

¯\_(ツ)_/¯

If what is is all that will ever be, imagine everything that will always be what is not.

[jkoritzinsky]

There's another way of editing array elements that would make it impossible to track the sorted state: editing the values of the elements in a pinned array. In those operations, there isn't even an array object that you're working with most of the time. You'd be working with C# pointers or an IntPtr to the data.

Also, any usage of native interop (which pins native arrays of blittable types) would basically make it impossible to make an IsSorted flag actually useful.

[benaadams]

Array's aren't primitive... so, why not?

They are pretty primitive

public static void SetArrayValues(int[] array)
{
    for (var i = 0; i < array.Length; i++)
    {
        array[i] = i;
    }
}

Generates

C.SetArrayValues(Int32[])
L0000: xor eax, eax
L0002: mov edx, [rcx+0x8]
L0005: test edx, edx
L0007: jle L0017

L0009: movsxd r8, eax            ; (loop start)
L000c: mov [rcx+r8*4+0x10], eax  ; array[i] = i
L0011: inc eax                   ; i++
L0013: cmp edx, eax              ; i < array.Length
L0015: jg L0009                  ; if true go to (loop start)
L0017: ret

Direct sequential memory access with no calls

[NonSecwitter]

I imagine the same thing that would happen anytime you lie to any function call. It won't work correctly.

if IsSorted cannot guarantee that the array has/has not been sorted I would think that it would barely change anything. Wouldn't it be the same as manually keeping track of whether the array has been sorted or not? It wouldn't add any significant value by adding it.

You make a good point. It would be better to not allow the Array to take something pre-sorted. This would actually alleviate the creator of the array from needing to do the sorting. Arrays could be instantiated un-sorted, require a comparer in order to use the sort function (have a default??? not sure on this), and the sort function on the instance is the only way to sort it.

All of those operations, sorting, maintaining knowledge of being sort, maintaining sort order... those ALL have to do with the internal structure and state of the array, which should be hidden from the user.

[NonSecwitter]

Array's aren't primitive... so, why not?

They are pretty primitive

public static void SetArrayValues(int[] array)
{
    for (var i = 0; i < array.Length; i++)
    {
        array[i] = i;
    }
}

Generates

C.SetArrayValues(Int32[])
L0000: xor eax, eax
L0002: mov edx, [rcx+0x8]
L0005: test edx, edx
L0007: jle L0017

L0009: movsxd r8, eax            ; (loop start)
L000c: mov [rcx+r8*4+0x10], eax  ; array[i] = i
L0011: inc eax                   ; i++
L0013: cmp edx, eax              ; i < array.Length
L0015: jg L0009                  ; if true go to (loop start)
L0017: ret

Direct sequential memory access with no calls

@benaadams okay, now show a call to access array.Length in an arbitrary place in code, where eax is _not_ already loaded with the value, where it still exists only in memory according to the abstract data structure that represents array and encapsulates the underlying pointer that abstracts away the actual location in memory of the sequential memory you're accessing

arrays are already abstract objects. Length is not part of a primitive of any type that I am familiar with.

[benaadams]

arrays are already abstract objects. Length is not part of a primitive of any type that I am familiar with.

Length is just before the first element of the array data

public static void SetFirstValueToLength(int[] array)
{
    var l = array.Length;
    array[0] = l;
}

C.SetFirstValueToLength(Int32[])
L0000: sub rsp, 0x28

L0004: mov eax, [rcx+0x8]  ; array.Length   (address rcx+0x8)
L0007: mov edx, eax
L0009: cmp eax, 0x0        ; Does array have at least 1 element
L000c: jbe L0016           ; if not, jump to throw

L000e: mov [rcx+0x10], edx ; array[0] = l;  (address rcx+0x10)
L0011: add rsp, 0x28
L0015: ret

L0016: call 0x7ffc49ff25f0 ; throw 0 offset is out of bounds
L001b: int3

To maintain an .IsSorted flag every write to the array in addition to being a straight mov write as above; it would also have to set .IsSorted to false; which would add cost to every array write from what happens currently, or validate it is still sorted by checking the elements either side which would be an even higher cost?

[NonSecwitter]

arrays are already abstract objects. Length is not part of a primitive of any type that I am familiar with.

Length is just before the first element of the array data

public static void SetFirstValueToLength(int[] array)
{
    var l = array.Length;
    array[0] = l;
}

C.SetFirstValueToLength(Int32[])
L0000: sub rsp, 0x28

L0004: mov eax, [rcx+0x8]  ; array.Length   (address rcx+0x8)
L0007: mov edx, eax
L0009: cmp eax, 0x0        ; Does array have at least 1 element
L000c: jbe L0016           ; if not, jump to throw

L000e: mov [rcx+0x10], edx ; array[0] = l;  (address rcx+0x10)
L0011: add rsp, 0x28
L0015: ret

L0016: call 0x7ffc49ff25f0 ; throw 0 offset is out of bounds
L001b: int3

To maintain an .IsSorted flag every write to the array in addition to being a straight mov write as above; it would also have to set .IsSorted to false; which would add cost to every array write from what happens currently, or validate it is still sorted by checking the elements either side which would be an even higher cost?

That reinforces the point that the array is an abstract data type. The implementation of Length is abstracted. array.Length isn't a primitive. It's not a handle for a memory address that provides a value immediately on lookup.

I don't claim to know the best implementation, but I see the potential for an implementation with minimal, but yes still real, overhead that improves the efficiency of the most common uses when averaged over the runtime of the application. Maybe the way you suggested, or maybe there's a different way. In either case, the Array is currently not a fully encapsulated class that adheres fully to data abstraction as long, but it could be.

[jkoritzinsky]

@NonSecwitter take a look at the code samples below:

unsafe
{
    var arr = new int[3] {1, 2, 3};
    fixed (int* ptr = arr)
    {
        arr[0] = 5;
    }
}

Here's an example using GCHandles and no unsafe code:

var arr = new int[3] {1, 2, 3};
GCHandle handle = GCHandle.Alloc(arr, GCHandleType.Pinned);
IntPtr ptr = handle.AddrOfPinnedObject();
Marshal.WriteInt32(ptr, 5);
handle.Free();

Here's a sample using Span<T>:

var arr = new int[3] {1, 2, 3};
Span<int> span = new Span<int>(arr);
Span<int> sliced = span.Slice(1, 1);
sliced[0] = 25;
span[0] = 5;

In each of these examples, we use APIs that can be used with many different types (not always arrays) and where the memory of the array is accessed directly via a pointer without going through the array object at all to change the value of an element in an array and make it unsorted. Only one of the cases requires you to use unsafe code.

Here's an example when passing an array to native code:

In a.cpp:

extern "C" void UpdateArrayElement(int* arr, int idx, int value)
{
    arr[idx] = value;
}

public class Native
{
    [DllImport("NativeLibrary")]
    private static extern void UpdateArrayElement(int[] arr, int idx, int value);

    public void ChangeArray(int[] arr, int idx, int value)
    {
           UpdateArrayElement(arr, idx, value);
    }
}

There is no way to know on the managed side how the call to the native UpdateArrayElement changes the array without re-inspecting the array when returning back to managed code. The amount of overhead that this would add is astronomical (having to iterate back over every array that is passed to native code, even for types that are represented the same in native and managed, possibly executing a user-provided comparator Length times even when the native code will not change the array contents).

Each of these code patterns are well-documented and entirely legal within C# and adding an IsSorted member to the array type and mantaining its validity would be nearly if not completely impossible.

[NonSecwitter]

@jkoritzinsky Okay, so C# is built in such a way to allow you to circumvent data encapsulation, so it may be incapable of fully and properly encapuslating an array in this way. It's a language limitation. I also concede that some people will call this a feature and find it functionally valuable.

Implementation could look different in a language that doesn't allow this, too. Another potential solution would be to create an ISortableArray with Sort(), SortedInsert(), and IsSorted as available functions, so long as _any_ unsorted write operation set the IsSorted property to false. That way, I could create a BinarySearch client that takes an ISortableArray and make good use of "IsSorted" and "Sort()".

But, if that can't apply to C# because it allows you to bypass encapsulation, then that is the final word on that. For what it's worth, there is a security implication to consider here, as well. An object that I pass to client code should only ever be accessible through the mechanisms explicitly provided by the object. If I want to create an array that only allows you to access the 1st, 3rd, and 5th element, I should be able to design the accessor methods to do this and not worry about anything getting around it.

[benaadams]

@NonSecwitter a different approach might be a new type that encapsulates an array; for example like SortedList<TKey, TValue> does?

[NonSecwitter]

@benaadams yea, that might work. I don't have an immediate need. I was reviewing some OOP theory and had an epiphany that "sorted" is a state condition and it's not included in the class implementation.

this operation in itself is not very demanding. (? represents the place of "IsSorted" in the objects structure)
mov [rcx+0x?], 0

i do realize that doing this A LOT of times could be significant. It could be noticeable if doing 1,000,000 inserts consecutively. but, it wouldn't be noticeable if I did a single or couple inserts here or there a moderate number of times through the life of the program. My usual cases for an array don't do large amounts of inserts consecutively, so maybe large jobs like that could be offloaded to another function somehow? Just thinking outside the box.

I still imagine there is probably a better way, but we're collectively pointing out how this CAN'T work rather than collectively working on how it COULD work. Maybe C# is a bad case to explore this.