{'fraction_non_alphanumeric': 0.03144896777927841, 'fraction_numerical': 0.007441911744439238, 'mean_word_length': 4.500606428138266, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The technique of in-place associative sorting

In the first place, a novel, yet straightforward in-place integer value-sorting algorithm is presented. It sorts in linear time using constant amount of additional memory for storing counters and indices beside the input array. The technique is inspired from the principal idea behind one of the ordinal theories of"serial order in behavior"and explained by the analogy with the three main stages in the formation and retrieval of memory in cognitive neuroscience: (i) practicing, (ii) storage and (iii) retrieval. It is further improved in terms of time complexity as well as specialized for distinct integers, though still improper for rank-sorting. Afterwards, another novel, yet straightforward technique is introduced which makes this efficient value-sorting technique proper for rank-sorting. Hence, given an array of n elements each have an integer key, the technique sorts the elements according to their integer keys in linear time using only constant amount of additional memory. The devised technique is very practical and efficient outperforming bucket sort, distribution counting sort and address calculation sort family of algorithms making it attractive in almost every case even when space is not a critical resource.


Introduction
The adjective "associative" derived from two facts where the first one will be realized with the description of the technique. The second one is that, although it replaces all derivatives of the content based sorting algorithms such as distribution counting sort [15,16], address calculation sort [17][18][19][20][21][22] and bucket sort [23,24] on a RAM, it seems to be more efficient on a"content addressable memory" (CAM) known as "associative memory" which in one word time find a matching segment in tag portion of the word and reaches the remainder of the word [29]. In the current version of associative sort developed on a RAM, the nodes of the imaginary subspace (tagged words) and the integers of the array space (untagged words) are processed sequentially which will be a matter of one word time for a CAM to retrieve previous or next tagged or untagged word.
An integer value-sorting algorithm puts an array of integers into ascending or descending order by their values, whereas a rank-sorting algorithm puts an array of elements (satellite information) into ascending or descending order by their numeric keys, each of which is an integer. It is possible that a rank-sorting algorithm can be used in place of a value-sorting algorithm, since if each element of the array to be sorted is itself an integer and used as the key, then rank-sorting degenerates to value-sorting, but the converse is not always true.
The technique described in this study is suitable for arrays where the elements are laid out in contiguous locations of the memory. Zero-based indexing is considered while accessing the elements, e.g., A[0] and A[n − 1] are the first and last elements of the array, respectively, where n is the number of elements of the array.
Nervous system is considered to be closely related and described with the "serial order in behavior" in cognitive neuroscience [6,7] with three basic theories which cover almost 2 all abstract data types used in computer science. These are chaining theory, positional theory and ordinal theory [8].
Chaining theory is the extension of reflex-chaining or response-chaining theory, where each response becomes the stimulus for the next. From an information processing perspective, comparison based sorting algorithms that sort the arrays by making a series of decisions relying on comparing keys can be classified under chaining theory. Each comparison becomes the stimulus for the next. Hence, keys themselves are associated with each other. Some important examples are quick sort [9], shell sort [10], merge sort [11] and heap sort [12].
Positional theory assumes order is stored by associating each element with its position in the sequence. The order is retrieved by using each position to cue its associated element. Conventional (Von Neumann) computers store and retrieve order using this method, through routines accessing separate addresses in memory. Content-based sorting algorithms where decisions rely on the contents of the keys can be classified under this theory. Each key is associated with a position depending on its content. Some important examples are distribution counting sort [15,16], address calculation sort [17][18][19][20][21][22], bucket sort [23,24] and radix sort [23][24][25][26].
Ordinal theory assumes order is stored along a single dimension, where that order is defined by relative rather than absolute values on that dimension. Order can be retrieved by moving along the dimension in one or the other direction. This theory need not assume either the item-item nor position-item associations of chaining and positional theories respectively [8].
One of the ordinal theories of serial order in behavior is that of Shiffrin and Cook [27] which suggests a model for short-term forgetting of item and order information of the brain. It assumes associations between elements and a "node", but only the nodes are associated with one another. By moving inwards from nodes representing the start and end of the sequence, the associations between nodes allow the order of items to be reconstructed [8].
The first technique presented in this study is in-place associative integer sorting [1][2][3][4]. Inspired from the ordinal model of Shiffrin and Cook, the technique assumes the associations are between the integers in the array space and the nodes in an imaginary linear subspace (ILS) that spans a predefined range of integers. The range of the integers spanned by the ILS is upper bounded by the number of integers n but may be smaller and can be located anywhere provided that its boundaries do not cross over that of the array. This makes the technique in-place, i.e., beside the input array, only a constant amount of memory locations are used for storing counters and indices. An association between an integer of the array space and the ILS is created by a node using a monotone bijective hash function that maps the integers in the predefined interval to the ILS. When a particular distinct integer is mapped to the ILS, a node is created reserving all the bits of the integer except for the most significant bit (MSB) which is used to tag the word as a node of the ILS for interrogation purposes. The reserved bits become the record of the node which then be used to count (practice) other occurrences of the particular integer that created the node. When all the key of the predefined interval are practiced, the nodes can be stored at the beginning of the array (short-term memory) retaining their relative order together with the information (cue) required to construct the sorted permutation of the practiced interval. Afterwards, the short-term memory is processed and the sorted permutation of the practiced interval is retrieved over the array space in linear time using only constant amount of additional memory.

4
Another ordinal theory is the original perturbation model of Estes [28]. Although proposed to provide a reasonable qualitative fit of the forgetting dynamics of the short term memory [8] in cognitive neuroscience, the principle idea behind the method is that the order of the elements is inherent in the cyclic reactivation of the elements, i.e., reactivations lead to reordering of the elements.
In-place associative integer sorting technique is an efficient in-place integer valuesorting algorithm, though not suitable for rank-sorting. Therefore, in-place associative permutation sort [5] technique is developed combining the principle idea behind the original perturbation model with the technique of associative integer sorting making it suitable for rank-sorting.

Definitions
The definition of rank-sorting is: given an array S of n elements, S To prevent confusion, the term "integer" is used while describing value-sorting techniques, whereas "key" is used for rank-sorting.
The notations used throughout the study are: (i) Universe of keys is assumed U = [0 . . . 2 w − 1] where w is the fixed word length.
(ii) Maximum and minimum keys of an array are, max(S) = max(a|a ∈ S) and min(S) = min(a|a ∈ S), respectively. Hence, range of the keys is, m = max(S) − min(S) + 1.
(iii) The notation B ⊂ A is used to indicated that B is a proper subset of A.

In-place Associative Integer Sorting
The most critical phase of associative integer sorting is derived from the cycle leader permutation (in-situ permutation) approach. Hence, a separate section is devised for it. Therefore, the simple monotone bijective hash function j = S[i] − δ that maps the keys to j ∈ [0, n − 1] can sort the array in O(n) time using O(1) constant space. This is cycle leader permutation where S is re-arranged by following the cycles of a permutation π.

Cycle Leader Permutation
First S[0] is sent to its final position π(0) (calculated by j = S[i] − δ). Then the element that was in π(0) is sent to its final position π(π(0)). The process proceeds in this way until the cycle is closed, that is until the key addressing the first position is found which means that the association 0 = S[0] − δ is constructed between the key and its position.

In-place Associative Distinct Key Sorting
If we look at the cycle leader permutation closer, we can interpret the technique entirely different. We are indeed creating an imaginary linear subspace Im[0 . . . n − 1] over S[0 . . . n − 1] where the relative basis of this imaginary linear subspace (ILS) coincides with that of the array space in the physical memory. The ILS spans a predefined interval of the range of keys and this interval is upper bounded by the number of keys n. Since the range of the keys m is equal to n, it spans the entire range of the keys. The association between the array space and the ILS is created by a node using the monotone bijective hash function j = S[i] − δ that maps a particular key to the ILS. Since ILS is defined over the array space, mapping a distinct key to the ILS is just an exchange operation from where a node is created. When a node is created for a particular key, the redundancy due to the association between the key and the position of the node releases the word allocated for the key in the physical memory. Hence, we can clear the node and set its tag bit, for instance its most significant bit (MSB) to discriminate it as a node for interrogation purposes, and use the remaining w − 1 bits of the node for any other purpose. When we want the key back to array space from the ILS, we can use the inverse of hash function and get the key back by S[i] = i + δ to the array space through the node. However, we don't use free bits of a node for other purposes during cycle leader permutation because it is known that all the keys are distinct and only one key can be mapped to a location creating a node. Therefore, instead of tagging the word as node using its MSB, we use the key itself to tag the word "implicitly" as node, since when a key is mapped to the imaginary subspace, it will always satisfy the monotone bijective hash function i = S[i] − δ. Hence, the keys are "implicitly practiced" in this case.
This interpretation immediately motivates a rank-sorting algorithm for distinct keys.
If m > n, it is not possible to construct a monotone bijective hash function that maps all the keys of the array into j ∈ [0, n−1] without collisions and additional storage space [33].
However, a bijective hash function can be constructed as a partial function that assigns all the keys in the range [δ, δ + n − 1] to exactly one element in j ∈ After implicitly practicing the keys in the predefined interval, the next step is to separate the array into practiced and unpracticed keys. This is simply a partitioning problem where we store implicitly practiced keys at the beginning of the array. However, instead of using a pivot for partitioning, we partition the keys that satisfy the hash function i = S[i] − δ. Hence, we obtain a simple two step sorting algorithm for distinct keys: The algorithm is surprisingly effective and efficient. Comparisons with Ω(n log n) quick sort [9,25] and merge sort [13] and heap sort [12,14]  Comparisons with value-sorting version of distribution counting sort (frequency counting sort [23]) showed that associative sort for distinct keys is superior in every case. This It is compared with radix sort [23][24][25][26] and bucket sort, as well. The results showed that it is superior than radix sort when m n ≤ 8 and faster than bucket sort for n distinct Finally, the dependency of the efficiency of the technique on the distribution of the keys is only O(n) which means it replaces all the methods based on address calculation [17][18][19][20][21][22], that are known to be very efficient when the keys have known (usually uniform) distribution and require additional space more or less proportional to n [26].

In-place Associative Integer Sorting
The technique introduced above that sorts distinct keys can be generalized to arrays with repeating integers if we consider using released w − 1 bits of a node for other purposes.
The generalized version becomes a value-sorting algorithm whereas the former was a rank-sorting algorithm. Henceforth, the term "integer" will be used instead of "key".
The main difficulties of all distributive sorting algorithms is that, when the integers are distributed using a hash function according to their content, several integers may be clustered around a loci, and several may be mapped to the same location. These problems are solved by inherent three basic phases of in-place associative integer sorting [1] namely (i) practicing, (ii) storage and (iii) retrieval.
We will consider the problem of sorting n integers S[0 . . . n − 1] each in the range . If m > n, it is not possible to construct a monotone bijective hash function that maps all the integers of the array into j ∈ [0, n − 1] without collisions and additional storage space. However, a bijective hash function can be constructed as a partial function that assigns all the integers in the range [δ, δ+n−1] to exactly one element in j ∈ [0, n−1].

Practicing
It is assumed that associations are between the integers in the array space and the nodes in an imaginary linear subspace (ILS) that spans a predefined range of integers. The ILS can be defined anywhere on the array space S[0 . . . n − 1] provided that its boundaries do not cross over that of the array. The range of the integers spanned by the ILS is upper bounded by the number of integers n revealing the asymptotic power of the technique with increasing n with respect to the range of integers. However, an ILS may be smaller and can be located anywhere over the array space making the technique in-place, i.e., beside the input array, only a constant amount of memory locations are used for storing counters and indices. An association between an integer and the ILS is created by a node using a monotone bijective hash function that maps the integers in the predefined interval to the ILS. Therefore, the monotone bijective hash function is a partial function that assigns to each distinct integer in a predefined interval to exactly one node of the ILS. Since ILS is defined over the array space, mapping a distinct integer to the imaginary subspace is just an exchange operation from where a node is created. This is "practicing a distinct integer of an interval". Once a node is created, the redundancy due to the association between the integer and the position of the node (the position where the integer is mapped) releases the word allocated to the integer in the physical memory except for most significant bit (MSB) which tags the word as a node for interrogation purposes. Hence, the integer is said to be sent to the ILS thorugh the node. Nevertheless, the tag bit discriminates the word as a node and the position of the node lets the integer be retrieved back through the node from the ILS using the inverse hash function. This is "integer retrieval" through the node from ILS. All the bits of the node except the tag bit can be cleared and used to store any information. Hence, they are the "record" of the node and the information stored in the record is the "cue" by which cognitive neuro-scientists describe the way that the brain recalls the successive items in an order during retrieval. For instance, it will be foreknown from the tag bit that a node has already been created while another occurrence of that particular integer is being practiced providing the opportunity to count other occurrences using the record. The process of counting an other occurrence of a particular integer is "practicing an idle integer of an interval". Repeating this process for all the integers of an interval is "practicing an interval", i.e., rehearsing used by cognitive neuroscientists to describe the way that the brain manipulates the sequence before storing in a short (or long) term memory. Practicing all the integers of an interval does not need to alter the value of other occurrences. Only the first occurrence is altered while being practiced from where a node is created. All other occurrences of that particular integer remain in the array space but become meaningless. That is why they are "idle integers".

Storage
Once all the integers in the predefined interval are practiced, the nodes are spread over the ILS depending on the distribution of the integers with relative order. The next step is to store the nodes in a systematic way closing the distance between them to a direction retaining their relative order with respect to each other. This is the storage phase of associative sort where the received, processed and combined information required to construct the sorted permutation of the practiced interval is stored in the short-term memory (beginning of the array). When the nodes are moved, it is not possible to retain the associations between the nodes of the ILS and the integers of the array space because the position of each node cues the recall of the corresponding integer and retrieve it 13 from the ILS using the inverse hash function. This motivates the idea to further use the record of a node to store the node's former position, or maybe its relative position with respect to the ILS or how much that node is moved relative to its absolute or relative position or the other integers. Unfortunately, this requires a record of a particular node is enough to store both the positional information of the node and the number of idle integers practiced by that node. This is statistically impossible, but, as mentioned before, further associations can be created using the idle integers that were already practiced by manipulating either their position or value or both. Hence, if the record is enough, it can store together the positional information and the number of practiced idle integers, whereas an idle integer can be associated accompanying the node to supply additional space to store the positional information if the record is not enough.
Let us assume for a moment that our universe of integers is w is the fixed word length and n ≤ 2 w−1 . We know that other occurrences of a particular integer can be counted (practiced) using w − 1 bits (record) of a node. If we decide to write the absolute position of a node into its record during storage, we need log n bits of the record. Hence, it is logical to think that we can count up to 2 w−1−log n − 1 idle integers with the record of a node during practicing. Fortunately, this is not the case.
We can count using all w − 1 bits of the record during practicing, and while storing the nodes at the beginning of the array (short-term memory), we can get an idle integer immediately after the node that has practiced at least 2 w−1−log n idle integers and write the absolute position of that node over the accompanying idle integer. In such a case, the  interval) which will prevent collisions while inserting idle integers immediately after the nodes that has practiced at least 2 w−1−log n idle integers during storage.

Retrieval
Finally, the sorted permutation of the practiced interval is constructed in the array space, using the information stored in the short-term memory. This is the retrieval phase of associative sort. It is known that if the record is enough, it stores both the position of the node and the number of practiced idle integers. If not, an associated idle integer accompanying the node stores the position of the node, whereas the record (predecessor of the idle integer) stores the number of practiced idle integers. If the number of occurrences of a particular integer is n i , then there are n i − 1 idle integers in the array space.
But the nodes represent the first integers that are mapped into the imaginary subspace through themselves. If all the idle integers are grouped on the right side of the short-term memory, then one can process the information in the short-term memory from right to left and distinguish whether there is an idle integer (untagged word) accompanying its predecessor (the node on the left side of the idle integer). An idle integer implies that it is accompanying the node on its left for additional storage. In such a case, the positional information is read from the idle integer, whereas the number of practiced idle integers is read from the record of the node. If there is not an idle integer accompanying the node, both the positional information and the number of practiced idle integers are read from the record of the node. Afterwards, the positional information cues the recall of the integer using the inverse hash function. This is "integer retrieval" from ILS. Hence, the retrieved integer can be copied on the array space as many as it occurrs. At this point, we have two options: sequential and recursive versions which will be described next.

Overall Algorithm
Consider n ≤ 2 w−1 integers S[0...n − 1] each in the range [0, 2 w−1 − 1]. All the integers in the range [δ, δ + n − ǫ − 1] will be practiced to Im[ǫ, n − 1] over S[ǫ, n − 1] where δ = min(S) and ǫ is calculated using Eqn. 3.2. Assume that there are n d nodes, n c idle integers practiced by those n d nodes and n ′ d = n − (n d + n c ) unpracticed integers that are out of the practiced interval. All these can be counted during practicing. Furthermore, the minimum δ ′ of the unpracticed integers can be found as well during practicing.
While n d nodes are being stored at the beginning of the array (short-term memory) closing the distance between them in order of precedence, if the record of a node is enough, i.e., the node has practiced less than 2 w−1−log n idle integers, we write the absolute (former) position of the node into its record together with the number of practiced idle integers.
Otherwise, we search to the right and get the first idle integer immediately after the node and write the absolute position of that node over the idle integer. Let us assume that ǫ ′

Sequential Version
Selecting the pivot equal to δ + n−ǫ−1, if n c −ǫ ′ idle integers and n ′ d unpracticed integers can be processed from right to left backwards and the integers practiced by each node can be copied over S[0 . . . n d + n c − 1] right to left backwards without collision with the short-term memory.

Recursive Version
We can recursively practice and store saving n d , ǫ ′ and δ in stack space. Although the exact number of integers to be sorted in the next level of recursion is n ′ d , the overall number of integers in that recursion is should return the total number of integers copied on the array to the higher level to let it know where it will start to expand its interval. It should be noticed that, in the recursive version of the technique, there is no need to partition n c − ǫ ′ idle integers from n ′ d unpracticed integers. Hence, one step is canceled improving the overall efficiency.

Relaxing the Restrictions
The technique of associative sorting is explained restricting the universe of integers to where w is the fixed word length and n ≤ 2 w−1 .
When an integer is first practiced, a node is created releasing w bits of the integer free. One bit is used to tag the word as a node. Hence, it is reasonable to doubt that the tag bit limits the universe of integers because all the integers should be untagged and in the range [0, 2 w−1 − 1] before being practiced. Of course we always have the option to use additional n bits to tag the nodes. However, we can, If practicing a distinct integer lets us to use its w − 1 bits to practice other occurrences of that particular integer, we have w − 1 free bits by which we can count up to 2 w−1 occurrences including the node that represents the first integer that created the node.
Hence, it is reasonable to doubt again that there is another restriction on the size of the arrays, i.e., n ≤ 2 w−1 under the assumption that an integer may always occur more than 2 w−1 times for an array of n > 2 w−1 . But an array can be divided into two parts in O(1) time and those parts can be merged in-place in linear time by [31] after sorted associatively.

Complexity
From complexity point of view, associative sort shows similar characteristics with distribution counting sort [15,16] and bucket sort [23,24]. In such a case, the time complexity is The average case is more difficult to estimate. However, fixing ǫ always to its maximum n/2 will let us to assert that the integers in the range [δ, δ + n 2 − 1] will be sorted in each step. On the other hand, if the integers are uniformly distributed, defining β = m n , we can say that n 2β integers will be in the range [δ, δ + n 2 − 1] in each step. Therefore, the algorithm will sort n 2β of the integers in O(n) time in each pass. This will continue until all the integers are sorted and the overall time complexity is, which means the algorithm is upper bounded by 2βO(n) or 2O(m) in the average case.

Empirical Tests
Practical comparisons for 1 million 32 bit integers with quick sort showed that associative sort is roughly 2 times faster for uniformly distributed integers when m = n. When m n = 10 performances are same. When m n = 1 10 associative sort becomes more than 3 times faster than quick sort. If the distribution is exponential, associative sort shows better performance up to m n ≈ 25 when compared with quick sort.
Practical comparisons for 1 million 32 bit integers showed that radix sort is 2 times faster for uniformly distributed integers when m = n. However, associative sort is slightly better than radix sort when m n = 1 10 . Further decreasing the ratio to m n = 1 100 , associative sort becomes more than 2 times faster than radix sort.
Practical comparisons for 1 million 32 bit integers showed that associative sort is 2 times faster than bucket sort with each bucket of size one hence distribution counting sort for m n = 1. Associative sort is still slightly better but the performances get closer when m n decreases. On the other hand, value-sorting version of distribution counting sort is 2 times faster than associative sort for m n = 1. Similarly, performances get closer when m n decreases.
Even omitting its space efficiency for a moment, associative sort asymptotically outperforms all content based sorting algorithms when n is large relative to m.

Improved In-place Associative Integer Sorting
With a very simple revision, the associative sorting technique can be improved theoretically and practically. The only cost of the improved version is that a recursive implementation is not possible.
The tag bit discriminates the word as a node in the array space after practicing. During right to left backwards without collision with the short-term memory. Afterwards, the tag bit of the processed node can be cleared and a new search to the left can be carried for the next node which will correspond to the next record S[n d − 2] of the short-term memory.
This can continue until all the integers are retrieved resulting in the sorted permutation of the practiced integers.
As the position of the node is not required during storage, there is no need to get an idle integer immediately after a node that has practiced at least 2 w−1−log n idle integers.
This means that ǫ is always zero. Hence, the improved version is capable of practicing the integers in the interval [δ, δ + n − 1] in each iteration. Therefore, while the former technique was capable of sorting integers that satisfy S where mod is the remainder modulo. In this case, w −1 integers may collide and mapped

In-place Associative Permutation Sort
In-place associative integer sorting introduced in the previous section is a value-sorting algorithm except the one for distinct integer keys (Section 3.2). All others are not suitable for rank-sorting which is the main objective of all sorting algorithms. In this section, in-place associative permutation technique will be introduced making the former technique suitable for rank-sorting without degrading its performance.
Although proposed to provide a reasonable qualitative fit of the forgetting dynamics of the short term memory [8] in cognitive neuroscience, the idea behind the original perturbation model of Estes [28] is that the order of the elements is inherent in the cyclic

Practicing
Only two new steps are added to practicing phase of associative integer sorting (Section 3.3.1) before permutation (reactivation) phase. These are (i) accumulation and (ii) re-practicing steps.
In accumulation step, all the records of the nodes are accumulated from left to right.
Hence, at the end, each record of a particular node keeps the exact position of the last idle key practiced by that node.
As mentioned previously, an ILS can create other subspaces and associations using the idle keys that were already practiced by manipulating either their position or value or both. Hence, it is logical to use the nodes of ILS as discrete hash functions that define the values of idle keys when they are re-practiced using the same monotone bijective hash function. This is the re-practicing step. When an idle key is remapped to its node, it can obtain its exact position (ticket) from the record of its node. The record of the node will be decreased by one for each re-practiced idle key. This means that, when all the idle keys of a particular node are re-practiced, the value of the node will point its exact position in the sorted permutation as well, of course when its MSB is ignored. Hence, when all the idle keys of all the nodes are re-practiced, all the idle keys and all the nodes (ignoring their MSB) will become consecutive, distinct and in the range [0, n d + n c − 1] pointing to their exact position in the sorted permutation.

Permutation (Reactivation)
After practicing, if the tag bits of the nodes are ignored, a simple cycle leader permutation can trivially rearrange the practiced keys at the beginning of array in order. Unsurprisingly each node precedes its own idle keys after this rearrangement. This simply puts the elements (satellite information) of the keys in order. However, the modified keys should be restored to their original values unless one intentionally wishes to normalize the keys and put all of them in the range [0, n − 1] at the end. Hence, the cycle leader permutation (reactivation) should take care of the nodes since the position of the nodes before reactivation is used to recall the key and retrieve it from the ILS using the inverse hash function. This immediately lets us to assert that if it would be possible to rearrange the practiced interval at the beginning of the array with each node storing its former position in its record, then it would be possible to restore all the modified keys to their original values. A node has a record of w − 1 bits which stores the node's exact position before the reactivation. Hence, while a node is being moved to its exact position, its former position can be overwritten into its record as the cue which can be used to recall the key using the inverse hash function. But, from information processing perspective, how one can distinguish the nodes that are already moved, from the nodes that are not moved yet in such a case? The idle and unpracticed keys (that are out of the practiced interval) are the solution to this problem. If a node is not at its exact position, then it is evident that either an idle or a key that is out of the practiced interval will address the position of that node.
Hence, a special outer cycle leader permutation that only reactivates the idle keys and the keys that are out of the practiced interval will ensure that the corresponding one will be moved to the actual position of the node giving a chance to start an inner cycle leader permutation that reactivates only the nodes and ensures that the nodes will be moved to their exact position storing their former position in their record as the cue. Once a node is moved to its exact position, there can not be any other outer cycle leader which will address that particular position. If another node is available where that particular node is moved, then the inner cycle leader permutation can continue with that node. However, if an idle or an unpracticed key is encountered, then the inner cycle leader permutation terminates and the outer cycle leader permutation continues.
From information processing perspective, associative permutation (reactivation) phase is a derivative of cycle leader permutation (Section 3.1) where the nodes, practiced idle

Restoring
With a final scan of the short-term memory (S[0 . . . n d + n c − 1]), one can obtain the exact values of practiced keys from their preceding nodes (tagged words). Each node stores its absolute position in its record (w − 1 bits) and cues the recall of the key using the inverse hash function. The value of the key can be copied over all the succeeding keys until a new node is found or the short-term memory ends.
28 for arrays where m > n 2 . On the other hand, it requires only O(1) additional space, making it time-space efficient compared to bucket sort and distribution counting sort.
The ratio m n defines its efficiency (time-space trade-offs) letting very large arrays to be sorted in-place. Furthermore, the dependency of the efficiency on the distribution of the keys is O(n) which means it replaces all the methods based on address calculation, that are known to be very efficient when the keys have known (usually uniform) distribution and require additional space more or less proportional to n. Hence, in-place associative permutation sort asymptotically outperforms all content based sorting algorithms making them attractive in almost every case even when space is not a critical resource.
The technique seems to be very flexible, efficient and applicable for other problems as well, such as hashing, searching, succinct data structures, gaining space, etc.
The only drawback of associative permutation sort is that it is unstable. However, as mentioned before, an imaginary subspace can create other subspaces and associations using the idle integers that were already practiced by manipulating either their position or value or both. Hence, different approaches can be developed to solve problems such as stability.

Discussion
Associative permutation sort first finds the minimum of the array and starts with the As a result, when the keys are sorted according to their most significant ⌈log n⌉ bits, in-place associative most significant ⌈log n⌉ radix sort is obtained. After the array is sorted according to their most significant ⌈log n⌉ bits, the idle keys are grouped and each group is preceded by the corresponding node that has practiced them. Hence, each group can be sorted sequentially or recursively assuming the satellite information as the key. If itself is used, it becomes an algorithm based on hash-and-conquer paradigm in contrast to divide-and-conquer. However, size of subgroups decreases and it may not be efficient when the ratio of range of keys in each subgroup to size of that subgroup, i.e., m n increases.
Hence, other strategies may need to be developed after the first pass.