Skip to main content

ArrayListTwinSorter

Short summary​

Implementation of TwinSort algorithm for ArrayList with performance optimizations. TwinSort is an adaptive, stable mergesort variant that optimizes naturally ordered pairs and reverse-ordered sequences through intelligent preprocessing.

Key features:

  • Preprocessing phase creates naturally sorted pairs
  • Reverses descending sequences to exploit existing order
  • Adaptive merge strategy with optimized boundary detection
  • O(n log n) worst case, O(n) best case for sorted data
  • Stable sort (maintains relative order of equal elements)
  • Optimized for real-world data patterns

Performance optimizations in this version:

  • Pre-allocated merge buffer to avoid repeated allocations
  • Buffer size tracking with 25% extra space to minimize reallocations
  • WHILE loops instead of FOR loops for better performance
  • State preservation between cycles to avoid redundant work
  • Optimized buffer management with size-based pre-allocation

The algorithm works by:

  1. Preprocessing: Identify and sort adjacent pairs, reverse descending sequences
  2. Adaptive merging: Skip unnecessary merges when sequences are already ordered
  3. Boundary optimization: Reduce work by detecting optimal merge boundaries
  4. Memory-efficient: Pre-allocated buffer with intelligent sizing

Based on research from lost-and-found-in-arrays repository, adapted for CNM Collections framework with real-time constraints and performance optimizations.

AccessAbstractFinalExtendsImplements
NoYesAbstractArrayListSorter-

UML Diagram​

Parameters

none

Properties​

className​

Type: CNM_AbstractObject.ClassName

This abstract property returns the class name of the concrete object, …

Methods​

clearContents​

  • Return type: VOID

This method is called in the destruct method and is intended to zero all references and interfaces that should not be destructed. …

clone​

This method is used to create a new instance…

FB_Exit​

  • Parameters:
    • bInCopyCode (BOOL): TRUE: the exit method is called in order to leave the instance which will be copied afterwards (online change).
  • Return type: BOOL

Mark the object as deleted, as it staiys in the memory.…

instantSort​

This method sorts the data structure instantly within one call. …

invertArray​

  • Parameters:
    • addressFirstElement (POINTER TO __XWORD)
    • addressLastElement (POINTER TO __XWORD)
  • Return type: VOID

Inverts the order of the elements inside the list. …

merge​

Merges two adjacent sorted sequences with adaptive boundary optimization.…

preprocessElements​

Preprocessing phase that creates naturally sorted pairs and reverses…

sort​

  • Parameters:
    • execute (BOOL): control bit to start or abort the sorting, needs to be active until the ExecutionState is SUCCESS
    • size (UDINT): The size of the list to be sorted
    • container (POINTER TO CNM_AbstractObject.IObject): the container, that contains the list elements
    • comparator (CNM_AbstractObject.IComparator): the comparator that should be used for the sort. Must not be changed while sort is in process
    • currentListVersion (__XWORD): the current version of the list, must change when the data in the list changes
  • Return type: CNM_ReturnTypes.SingleExecutionState

This method sorts the ArrayList using the TwinSort algorithm.…

Code​

Declaration​

{attribute 'enable_dynamic_creation'}
FUNCTION_BLOCK FINAL ArrayListTwinSorter EXTENDS AbstractArrayListSorter
VAR
	// Merge buffer for temporary storage during merges - pre-allocated
	mergeBuffer :POINTER TO CNM_AbstractObject.IObject;
END_VAR