Hello,
I am really unable to understand the intuition behind the working of sorting algorithm, I do understand the code and its output at every step, but how is this sorting working in the first place?
The use of ticker and sticker specially?
Regards,
Hi @Aaditya1
The main idea is that you want to sort buckets, for example the 2 buckets hashes in the lab:
First bucket hash contains values 0123 and the second 4567 (offset by 4).
For sorting it and āunsortingā we use ticker (indexes of the values):
This ticker will help us track where the values āmoveā. When we sort the buckets, we get this sticker:
Meaning the lowest value in the first bucket hash is index 0, the second lowest value is index 4 and so on.
To undo the sort we also keep track of the undo_sort variable:
Meaning that after sorting, to get back we want to take the first value at index 0, the second value at index 2, the third value at index 4 and so on.
When I wanted to understand the whole lab I implemented it in Excel (you can do it on paper if you prefer).
Hereās the whole sequence of sorting and shuffling:
Later in the Assignment it gets more complicated so itās better to understand it now.
Cheers
Hey @arvyzukai,
An intriguing explanation indeed, thanks for sharing it 
Cheers,
Elemento
You explained it brilliantly @arvyzukai , but apart from this my one more pain point is why does this idea of āseqlen*buckets + ticker%seqlenā work at the first place for sorting?
Is this a standard way to sort or something else, what is the reason for choosing that expression?
Thatās a good question 
I corrected my response that might have caused the confusion because of my lapse of using ābucketsā instead of āhashesā (and not mentioning the offset).
So to answer why it works - is because the buckets in the second hash are offset by the number of buckets (4) so when we multiply by sequence length (seqlen*buckets), the minimum value in the second hash will never be lower than the max value in the first (31 vs. 32) and with the +ticker%seqlen part in the equation is becomes the āinner battleā for position in the hash. (note the grey background row in the full picture)
I cannot answer this question competently because sorting algorithms is a research field on itās own and I donāt have the expertise but my intuition lies that itās just a simple arithmetic that works - computers do math pretty quickly (working with indexes) while moving stuff in the memory (moving values in list etc.) is slow. But I would ask someone else more competent on this.
Cheers
Thanks a lot!! Now I get it fully.
Regards,
Thanks @arvyzukai . My interpretation was that the +ticker%seqlen operation was required to make the sort stable (meaning that repeated invocations of the sort method would not result in a different ordering due to breaking ties randomly).
Your interpretation is correct and is the more elegant way than saying āinner battleā 
Thanks for pointing that out!
