A possible implement of Deque::sort

[FrozenLemonTee]

Is your feature request related to a problem? Please describe. Missing Deque::sort Related issue: #2706

Describe the solution you'd like

pub fn[A : Compare] sort(self : Deque[A]) -> Unit {
  let total_len = self.length()
  
  // Case 0: Empty
  if total_len == 0 {
    return
  }
  
  let (left_view, right_view) = self.as_views()
  
 // Array provides APIs for Deque to call quick_sort
 // Case 1: Only the left view has data (already continuous)
  if right_view.length() == 0 {
    Array::quick_sort(left_view, None, get_limit(left_view.length()))
    return
  }
  
 // Case 2: Only the right view has data (already continuous)
  if left_view.length() == 0 {
    Array::quick_sort(right_view, None, get_limit(right_view.length()))
    return
  }
  
  // Case 3: Both views have data, make them contiguous through reserve_capacity
  self.reserve_capacity(total_len)
  
  let new_left_view = self.as_views().0
  
  Array::quick_sort(new_left_view, None, get_limit(new_left_view.length()))
}

[Lampese]

IMO it may be acceptable for Deque not to provide sort, but my considerations may not be comprehensive. But adding sorting algorithms would cause Deque's volume to expand excessively.

[peter-jerry-ye]

Let's put sort aside for now. In Rust it's implemented through make_contigous, which we don't have and can't provide for now cc @bobzhang

[peter-jerry-ye]

Let's try to have a locally defined ArraySlice or something like that and provide the make_contigous method.

[peter-jerry-ye]

After #2880 we should move this forward.