Proposal: replace the naive quick sort for vec with sort for array

[yjl9903]

In this pr #72 , author implemented an optimized quick sort algorithm like the std:sort in C++

But for vec, it already has a naive quick sort implementation

core/vec/vec.mbt

Lines 619 to 639 in bcb5d5c

	/// Quicksort helper
	fn quicksort[T : Compare](self : Vec[T], left : Int, right : Int) -> Unit {
	if left <= right {
	let idx = self.partition(0, right)
	self.quicksort(left, idx - 1)
	self.quicksort(idx + 1, right)
	}
	}
	/// Sort the vector in place.
	///
	/// This implementation uses the quicksort algorithm.
	///
	/// # Example
	/// ```
	/// let v = Vec::[3, 4, 5, 1, 2]
	/// v.sort()
	/// ```
	pub fn sort[T : Compare](self : Vec[T]) -> Unit {
	self.quicksort(0, self.len - 1)
	}

I think we can replace the vec sort with directly using the sort impl from array module, not implementing it twice.

[yjl9903]

I am trying to contribute, but I encountered a problem

self.buf.0 is Array[UnsafeMaybeUninit[T]], is it possible "casting" it to Array[T] (for that we should do sort inplace, and ensure self.buf from 0 to self.len - 1 does have value)? Or any other possible solutions?

[bobzhang]

self.buf.0 is Array[UnsafeMaybeUninit[T]], is it possible "casting" it to Array[T]

This is impossible in the wasm backend, the wasm will have its own verification layer.
You can define a local trait and use generics to share the code?

[yjl9903]

@bobzhang Thanks. But if I did not misunderstand, there should be a generic trait here which Array[T] and Vec[T] should implement? But moonbit seems not support it now?

Is it impossible (for I am not very familiar with related PL / type system knowledge)? Or moonbit has planned to implement it in the future?

https://github.com/moonbitlang/core/blob/main/array/sort.mbt

[Lampese]

#112 I think the discussion in this PR might be helpful.

[Lampese]

#168

[bobzhang]

done in master