# Integrating Pareto Optimization into Dynamic Programming
## 3 Three Integration Strategies and Their Variants
### Sorting Variants within SORT  
Sorting (in our context, sorting always means lexicographic sorting in \(A\times B\) according to \((>_{A},\ >_{B})\)) algorithms are traditionally classified along different criteria. Next to runtime complexity, the memory usage of the algorithms is very important in the context of dynamic programming. An algorithm can either operate in-place, taking \(O(\log(N))\) or less in additional memory, while algorithms that are not in place need worst case \(O(N)\) memory or more. Here, we introduce also a third category of algorithms that will not move around elements that are already sorted, but technically are not in-place, contrasting with implementations that will copy or move every element once regardless of position. Another interesting aspect is the adaptiveness, as even non-adaptive algorithms can show adaptive behavior. Most of the following algorithms are adaptive in the sense that they work on known sorted sublists. Other factors, such as stability, are not important for this work and will therefore not be discussed. [PERSON]'s GAP reads grammars and algebras written in GAP-L and generates code in C++. Defined by other constraints and validated before this work, the _deque_object of the C++ STL library definitions is used by [PERSON]'s GAP for holding lists of intermediate results. This gives a hard constraint on which algorithms can work efficiently and which cannot. A _deque_ can be regarded as an array that is potentially fragmented across memory. This guarantees element access in \(O(1)\) time, while insert or erase operations have \(O(N)\) time complexity, except when executed on the first or last element of the list. Two competing strategies for sorting intermediate results during dynamic programming will be discussed in this work. Algorithm 1 Quicksort: If nothing is known about the content of the list, Quicksort is widely recognized to be one of the fastest algorithms for comparison-based sorting. The C++ STL library (the definitions of GNU were used) contains an implementation of Quicksort with a cut-off and Insertionsort for smaller problems as proposed by [PERSON] [26]. It can be considered to run in-place with an average runtime complexity of \(O(N\log(N))\), while the worst case is \(O(N^{2})\). Empirically, Quicksort can be shown to be adaptive to pre-sorted sublists [27], shortening computation times with increasing sortedness. In a dynamic programming scenario, already sorted sublists may be known within the overall list. This knowledge can possibly be used within the sorting algorithms. Let \(N\) be the total number of all list elements over all sorted sublists and \(M\) the number of sublists that have to be merged. Merging two sublists of length \(l_{1}\) and \(l_{2}\) results in sorted list of length \(l=l_{1}+l_{2}\), w.l.o.g. \(l_{1}\leq l_{2}\). Algorithm 2 List-Join: The most intuitive algorithm to merge \(M\) sorted lists is to iteratively build a new list, for each element testing which element of the \(M\) sublists needs to be added next. This gives a trivial complexity of a guaranteed runtime of \(O(N\cdot M)\) and space complexity of \(O(N)\). Disregarding of initial position, every element needs to be moved to the new list during the merge. Algorithm 3 Queue-Join: The behavior of List-Join can be improved by using a sorted queue to find the next element to be added. Inserting into a sorted container has a complexity of \(O(\log(M))\), effectively reducing the complexity of the whole merge to \(O(N\log(M))\), while the space complexity remains unchanged. Algorithm 4 In-Join: The In-Join algorithm was developed to reduce the number of elements that have to be moved in memory during the merge. Its basic functionality is the same as List-Join, but each element is written directly to the correct position of the input list if necessary, otherwise left untouched. This, however, creates the need for a temporary element queue of displaced candidates. Even worse, elements do not need to be inserted into the queue in order.