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.


(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.


closed as off-topic by Joshua Grochow, Aryeh, Marzio De Biasi, Gamow, Peter Shor Dec 21 '18 at 12:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Joshua Grochow, Aryeh, Marzio De Biasi, Gamow, Peter Shor
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ This is not a research-level problem. $\endgroup$ – xrq Dec 21 '18 at 4:06

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.


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.
        sortedWorking = [],
        nextIndex = [],
        maxNumberOfCollisions = arrayToSort.length - 1

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

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

    for (var index in arrayToSort)
            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


Not the answer you're looking for? Browse other questions tagged or ask your own question.