<p>This question is far from research level. Comparison sorts cannot have better than <span class="math-container">$O(n\log n)$</span> worst-case complexity. The proof is easily found in any algorithms textbook.</p>

<p>Non-comparison sorts potentially could be faster, but they have a limited domain, e.g. integer arrays.</p>

CC BY-SA 4.0
2018-12-21T04:10:29.810Z
2018-12-21T04:10:29.810Z
xrq
<p>If sparse arrays worked like magic, then yes, theoretically this is possible. Consider the following example implemented in JavaScript:</p>



<pre><code>//arrayToSort = array of positive integers where 
//the largest number in the array * (array.length - 1) is less than (2^32)-1
function galacticSort(arrayToSort)//noSortSort //BASICsort //sparSort //memSort
{
    /*
       This works similar to how line numbering works in BASIC.
       In basic you never number your lines 1,2,3,4 because if you want to come back 
       later and insert another line you have to renumber your lines. So in BASIC,
       you number your lines with a multiple of how many lines you anticipate you may 
       want to insert later. Eg 10, 20, 30, 40 - giving you 9 lines you can insert 
       or 100, 200, 300, 400 to give you 99 lines you can insert in between

       So in this example, we give each number that we are sorting a place in an array 
       that is equal to its value and put it there. But since there might be duplicate 
       entry (like there might be lines in BASIC that need to be inserted later), 
       there needs to be room after each number so that a duplicate number can be 
       inserted after it. So the actual position of the number you are sorting 
       is not equal to its value but equal to its value * (arrayToSort.length - 1) 

       And it is length-1 because if the array had all the same values, 
       the gap in between wouldn't matter but if the array had all the same values 
       except for one element then the gap would need to be the length of the array 
       minus 1. You could make this number smaller and thus allow larger numbers to be 
       processed if you had knowledge of the number of duplicate entries contained in 
       the array because that is what array.length-1 or maxNumberOfCollisions stands for.
    */
    var 
        sortedWorking = [],
        nextIndex = [],
        maxNumberOfCollisions = arrayToSort.length - 1
    ;

    function nextAvailableIndexForValue(value)
    {
        if(nextIndex[value] &gt;= 0)
        {
            //return then increment for next time
            return nextIndex[value]++;
        }
        else
        {
            //set for first time
            nextIndex[value] = maxNumberOfCollisions * value;

            //return then increment for next time
            return nextIndex[value]++;
        }
    }

    for (var index in arrayToSort)
    {
        var 
            value = arrayToSort[index],
            newIndex = nextAvailableIndexForValue(value)
        ;
        sortedWorking[newIndex] = value;
    }

    return sortedWorking;
}
</code></pre>

<p>Unfortunately due to the only possible ways to physically implement sparse arrays, this method is impractical because the <code>sortedWorking</code> array that gets returned is not actually in order in memory (unless <code>sortedWorking</code> is sorted as the elements are inserted or when it is iterated over after being returned which defeats the purpose of this sorting algorithm). </p>

<p>Albeit it does work on a conceptual level which is kinda cool</p>

CC BY-SA 4.0
2018-12-21T00:31:24.657Z
2018-12-21T00:31:24.657Z
zoplonix
<p>Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted. </p>

<p><a href="https://i.sstatic.net/f5bMf.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/f5bMf.gif" alt="quicksort"></a></p>

<p>(notice how many times the 2 is touched [circled in red and moved] before the array is considered sorted)</p>

<p>So would it be theoretically possible to have a sorting algorithm that doesn't have to touch each source element more than once, thus making it quicker (ie less steps: eg the fewest steps possible) to compute?</p>

<p>From what I understand, every sorting algorithm on the planet requires that each source element has to be touched more than once before the array is considered sorted.</p>

CC BY-SA 4.0
2018-12-21T04:06:23.873Z
This is not a research-level problem.
xrq
<cc.complexity-theory><ds.algorithms><np-hardness>
Is it possible to have a sorting algorithm that computes faster than QuickSort?
zoplonix
# Is it possible to have a sorting algorithm that computes faster than QuickSort?

(Asked by: username_0 on 2018-12-21)

Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted.

[![quicksort](https://i.sstatic.net/f5bMf.gif)](https://i.sstatic.net/f5bMf.gif)

(notice how many times the 2 is touched [circled in red and moved] before the array is considered sorted)

So would it be theoretically possible to have a sorting algorithm that doesn't have to touch each source element more than once, thus making it quicker (ie less steps: eg the fewest steps possible) to compute?

From what I understand, every sorting algorithm on the planet requires that each source element has to be touched more than once before the array is considered sorted.

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness
> **Comments:**
> **username_1**: This is not a research-level problem.  

---

## 2 answers

### Answer by username_1 on 2018-12-21. Score: 2

This question is far from research level. Comparison sorts cannot have better than $O(n\log n)$ worst-case complexity. The proof is easily found in any algorithms textbook.

Non-comparison sorts potentially could be faster, but they have a limited domain, e.g. integer arrays.


---

### Answer by username_0 on 2018-12-21. Score: -3

If sparse arrays worked like magic, then yes, theoretically this is possible. Consider the following example implemented in JavaScript:
//arrayToSort = array of positive integers where 
//the largest number in the array * (array.length - 1) is less than (2^32)-1
function galacticSort(arrayToSort)//noSortSort //BASICsort //sparSort //memSort
{
    /*
       This works similar to how line numbering works in BASIC.
       In basic you never number your lines 1,2,3,4 because if you want to come back 
       later and insert another line you have to renumber your lines. So in BASIC,
       you number your lines with a multiple of how many lines you anticipate you may 
       want to insert later. Eg 10, 20, 30, 40 - giving you 9 lines you can insert 
       or 100, 200, 300, 400 to give you 99 lines you can insert in between

       So in this example, we give each number that we are sorting a place in an array 
       that is equal to its value and put it there. But since there might be duplicate 
       entry (like there might be lines in BASIC that need to be inserted later), 
       there needs to be room after each number so that a duplicate number can be 
       inserted after it. So the actual position of the number you are sorting 
       is not equal to its value but equal to its value * (arrayToSort.length - 1) 

       And it is length-1 because if the array had all the same values, 
       the gap in between wouldn't matter but if the array had all the same values 
       except for one element then the gap would need to be the length of the array 
       minus 1. You could make this number smaller and thus allow larger numbers to be 
       processed if you had knowledge of the number of duplicate entries contained in 
       the array because that is what array.length-1 or maxNumberOfCollisions stands for.
    */
    var 
        sortedWorking = [],
        nextIndex = [],
        maxNumberOfCollisions = arrayToSort.length - 1
    ;

    function nextAvailableIndexForValue(value)
    {
        if(nextIndex[value] >= 0)
        {
            //return then increment for next time
            return nextIndex[value]++;
        }
        else
        {
            //set for first time
            nextIndex[value] = maxNumberOfCollisions * value;

            //return then increment for next time
            return nextIndex[value]++;
        }
    }

    for (var index in arrayToSort)
    {
        var 
            value = arrayToSort[index],
            newIndex = nextAvailableIndexForValue(value)
        ;
        sortedWorking[newIndex] = value;
    }

    return sortedWorking;
}

Unfortunately due to the only possible ways to physically implement sparse arrays, this method is impractical because the sortedWorking array that gets returned is not actually in order in memory (unless sortedWorking is sorted as the elements are inserted or when it is iterated over after being returned which defeats the purpose of this sorting algorithm). 
Albeit it does work on a conceptual level which is kinda cool


---

