Draft:Darksort

• Comment: Other than the author's own paper, I'm finding essentially nothing in the literature that talks about darksort. Most of the references in this article are about other sorting algorithms.
  Statements such as "Darksort definitively wins against bucket sort as bucket sort has a worst-case complexity of O(n2)" are extremely naive. Worst-case performance is only one of many different criteria by which algorithms can be compared. -- RoySmith (talk) 20:00, 15 April 2020 (UTC)

• Comment: Instances addressing the reader such as "As you can see" do not adopt an encyclopedic tone. Furthermore, avoid non-formal uses of language such as "Not much needs to be discussed since it beats it in Big-O complexity."
  Furthermore, please link to other sorting articles such as counting and pigeonhole. GeneralPoxter (talk) 21:02, 21 October 2019 (UTC)

• Comment: Terms like "the fastest integer sorting algorithm" "darksort beats all other linear sorting algorithms in software" " the fastest software sorting algorithm in the world" "darksort wins every time" are not acceptable in a neutral encyclopedia article. Theroadislong (talk) 20:18, 1 August 2019 (UTC)

---

Darksort

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 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
    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. It is an integer sorting algorithm. It beats every linear sorting algorithm in speed, although the space complexity may be larger than others.