Draft:Darksort 2

Darksort 2

Class	Sorting Algorithm
Data structure	Array
Worst-case performance	$O(n+max)$
Worst-case space complexity	$O(n+max)$

Darksort is a sorting algorithm that was first introduced in a paper published in the International Journal of Soft Computing and Engineering in May 2018. The algorithm is designed to sort integer values and has a time and space complexity of O(n), making it a linear sorting algorithm.

The algorithm works by first creating a direct-access table (DAT) that stores the number of occurrences of each unique value in the input array. The DAT is then used to create a sorted array, which is returned as the output of the algorithm.

It uses advanced data structures to improve speed in sorting. It is an integer sorting algorithm. It takes in an unsorted or sorted array Array and an integer Arraysize that describes the size of the array, as well as max in <maxvariant>.

Algorithm (in Python)

Standard darksort

def DarksortDat(Array, Arraysize):
    max = 0;
    for i in range(0, Arraysize):
        if (max < Array[i]):
            max = Array[i]
    newarray = [0] * (max+1)
    for i in range(0, Arraysize):
        newarray[Array[i]] += 1
    count = 0
    for i in range(0, (max + 1)):
        var = newarray[i]
        while (var > 0):
            Array[count] = i
            count += 1
            var -= 1
    return Array

Max variant darksort

def DarksortDat<maxvariant>(Array, Arraysize, max):
    newarray = [0] * (max+1)
    for i in range(0, Arraysize):
        newarray[Array[i]] += 1
    count = 0
    for i in range(0, (max + 1)):
        var = newarray[i]
        while (var > 0):
            Array[count] = i
            count += 1
            var -= 1
    return Array

Darksort has several variants:

Direct-access table darksort (original darksort)

The original darksort algorithm uses a direct-access table (DAT) to store the number of occurrences of each unique value in the input array. The DAT is then used to create a sorted array.

AVL darksort

This variant uses an AVL tree to store the sorted data, allowing for efficient searching and insertion operations. This variant has the advantage of being able to perform various operations, such as searching and inserting, in logarithmic time.

Heap darksort

This variant uses a heap to store the sorted data, enabling near-constant time retrieval of data. This variant is useful for applications where data needs to be retrieved in a near-constant fashion, such as serving advertisements to clients.

General Data Structures

Darksort can be extended to any data structure that can create and insert. This variant allows Darksort to be extended to any data structure that supports creation and insertion operations. In general, DarksortDAT is the most important variant, but data structure versions can improve space complexity. The space complexity is exactly two times the size of the input array as well as gaps included in the max array finalarray. The space complexity is large because darksort holds gaps for numbers that are missing in the data set in memory.

General data structures darksort

def DarksortGDS(Array, Arraysize):
    max = 0;
    for i in range(0, Arraysize):
        if (max < Array[i]):
            max = Array[i]
    newarray = [0] * (max+1)
    for i in range(0, Arraysize):
        newarray[Array[i]] += 1
    Create.GDS #(AVL or Heap for example)
    for i in range(0, (max + 1)):
        var = newarray[i]
        while (var > 0):
            GDS.insert(i)
            var -= 1
    return GDS

Darksort is a stable sorting algorithm. It can be changed to descending order by iterating backwards over the newarray in the final for loop.

Space Complexity of Darksort

The space complexity of Darksort is O(n), which means that the amount of memory required by the algorithm grows linearly with the size of the input array. However, the space complexity can be improved by using data structures such as AVL trees or heaps.

Comparison to other linear sorts

Darksort is superior to other linear sorting algorithms under certain circumstances. For example, darksort is faster than counting sort when there are not too many gaps in the data. Darksort is also faster than radix sort when the word size is large and the keys are highly distinct.

Conclusion

Darksort is a unique linear sorting algorithm with superior performance to all other linear sorting algorithms under certain circumstances, although the space complexity may be larger than others. It is an integer sorting algorithm.

References

This page will be placed in the following categories if it is moved to the article namespace.

Categories:

• Computer science