search

Roblox / Core-Scripts

All of ROBLOX's core client scripts.
Apache License 2.0
247 stars 182 forks source link

What is the point of MergeSort.lua? #888

Closed Kampfkarren closed 7 years ago

Kampfkarren commented 7 years ago

https://github.com/Roblox/Core-Scripts/blob/master/CoreScriptsRoot/MergeSort.lua

I noticed this file while clicking around. What's the point of this? Why not just use table.sort? Why use MergeSort of all sorting algorithms? table.sort already uses QuickSort.

Fraktality commented 7 years ago

The advantage mergesort has over quicksort is that mergesort is stable (i.e. preserves the order of equal-valued elements)

Kampfkarren commented 7 years ago

What's the advantage of that?

kyle-emmerich commented 7 years ago

Things like UIListLayout call it because it's faster to keep the whole sort in Lua than it is to continually call a sort order callback. In general, it's fairly slow for C++ to call a Lua function.

It's merge sort because you need the order to stay the same every time, or elements would jump around on screen.

Kampfkarren commented 7 years ago

Hm, alright. Closed.