On 1 May 2021, at 17:06, Jian He wrote:
Been self study Database, from database I deep dived into sorting algorithms.
Databases can do in-memory QuickSort. It also has an on-disk MergeSort.
For MergeSort: I follow this tutorial https://youtu.be/6pV2IF0fgKY?t=1108
(around 1 minutes only)
Also check https://en.wikipedia.org/wiki/Merge_sort
But I am still not fully understanding about nlogn. I understand how many
passes it will take, that is* logn. *
Yes each pass will sort N elements.
But I still don't get the N stand for in nlogn.*
So, answering the question…
The ’n’ refers to the need to do something to each element at least once, so the sort time grows in simple proportion to the size of the list that needs to be sorted. Unfortunately that is not enough work to get the list sorted so extra steps are needed. The log(n) indicates how many extra steps are needed. So the overall performance is proportional to the number of elements (N) multiplied by the log of the number of elements, viz., N * log(N)
Regards
Gavan Schneider
——
Gavan Schneider, Sodwalls, NSW, Australia
Explanations exist; they have existed for all time; there is always a well-known solution to every human problem — neat, plausible, and wrong.
— H. L. Mencken, 1920