Thanks a lot. I found out about this Youtube video (https://youtu.be/alJswNJ4P3U?t=1852), in case you guys are interested. This video really clarify about the time complixty of MergeSort.
On Sat, May 1, 2021 at 3:19 PM Gavan Schneider <list.pg.ga...@pendari.org> wrote: > 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 >
