I'm studying malloc and free and writing my own malloc and free. But when I read about the different algorithms (best fit, first fit, worst fit) then it doesn't say which algorithm is used for searching and which is used for sorting.
The best fit strategy is quite simple: first, search through the free list and find chunks of free memory that are as big or bigger than the requested size. Then, return the one that is the smallest in that group of candidates; this is the so called best-fit chunk (it could be called smallest fit too). One pass through the free list is enough to find the correct block to return. The intuition behind best fit is simple: by returning a block that is close to what the user asks, best fit tries to reduce wasted space. However, there is a cost; naive implementations pay a heavy performance penalty when performing an exhaustive search for the correct free block.
I hope best fit uses some sort of binary search to find the best fit, is it so or what is the data structure of the free list? If we arrange the free list as a graph then we can binary search it for the best fit and it would take O(log n) to find the best fit among n chunks. Is it that way, better or worse?