optimize: use C implement quick sort

[liuq19]

We want use C implement quick sort for higer performance.

The origin go implement is https://github.com/bytedance/sonic/blob/main/encoder/sort.go#L21

[Monib007]

Hey would you assign me this task? I'm just beginning to open source and I'd like to contribute.

[liuq19]

Sure, Welcome~

[liuq19]

Currently, Sonic has implemented a fast string sorting algorithm in Golang, which can be ported to C language for further optimization of sorting time. The specific sorting algorithm can refer to the existing Golang implementation in Sonic, which has implemented the 3-way Radix Quicksort. The code can be found at https://github.com/bytedance/sonic/blob/main/encoder/sort.go#L21.

You can implement quick-sort as follows:

typedef struct MapPair{
GoString key;
void* value;
} MapPair;

// The following interface is used to swap MapPair.
void swap(MapPair* lhs, MapPair* rhs) {
MapPair temp;
temp = *lhs;
*lhs = *rhs;
*rhs = temp;
}

// Sort the MapPair array kvs by the string key, n is the length of MapPiar array.
// Implement the quick-sort algorithm in a non-recursive way. 
// A Stack data structure needs to be implemented for non-recursive implementation. The max stack depth may be 4096.
// If the stack space is exceeded, return an error -1, otherwise return 0.
long quick_sort(MapPair* kvs, size_t n, Stack* stk) {

}