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 f*or in n*logn.*
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