how efficient is sorting and searching in malloc/free?

Most modern implementations of malloc are extremely efficient without using linear-time fitting strategies and instead can often use constant-time operations. See slab allocators as an example.

That said, I've noticed you seem to have an interest in writing a faster memory allocator than malloc. I hope you don't mind but I think that's a very counter-productive idea. When you try to match all the requirements of malloc like thread-safety and the ability to allocate and free arbitrary-sized memory blocks, it's almost unbeatable (maybe a computer architecture expert from Intel or something might be able to come up with something mildly better). Besides that, it's usually not the allocation algorithm that costs so much as, say, the page faults and compulsory cache misses incurred in the process of loading that memory which is an unavoidable cost whenever you request new memory from the heap.

The easiest way to get more performance out of code bottlenecked by malloc and free is to simply use these less often. You can allocate a huge chunk of memory and then just pool it to the areas in your code that need it, potentially in a straightforward sequential fashion (be careful about alignment) if you don't need to free the memory of individual chunks until you're done with the operation (at which point you can free all the pooled memory at once), or say, using a free list if all the memory blocks you are allocating are of the same size (in which case you don't even have to worry about alignment). And if you know you only need that for a given thread, you can pool the memory in a lock-free fashion.