Re: database sorting algorithms.

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