# Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]

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.

• This is not a research-level problem. – 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.
*/
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