Drop-Merge Sort

function dropMergeSort(arr) {
  const dropped = [];
  let i = 1;
  while (i < arr.length) {
    if (arr[i] < arr[i - 1]) {
      dropped.push(arr.splice(i, 1)[0]);
    } else i++;
  }
  dropped.sort((a, b) => a - b);
  // Merge arr and dropped back together
}

def drop_merge_sort(arr):
    dropped = []
    i = 1
    while i < len(arr):
        if arr[i] < arr[i - 1]:
            dropped.append(arr.pop(i))
        else: i += 1
    dropped.sort()
    # Merge arr and dropped

void dropMergeSort(vector<int>& arr) {
  vector<int> dropped;
  auto it = arr.begin() + 1;
  while (it != arr.end()) {
    if (*it < *(it-1)) {
      dropped.push_back(*it);
      it = arr.erase(it);
    } else ++it;
  }
  sort(dropped.begin(), dropped.end());
  // Merge arr and dropped
}

void DropMergeSort(List<int> arr) {
  var dropped = new List<int>();
  int i = 1;
  while (i < arr.Count) {
    if (arr[i] < arr[i-1]) {
      dropped.Add(arr[i]); arr.RemoveAt(i);
    } else i++;
  }
  dropped.Sort();
  // Merge arr and dropped
}

void dropMergeSort(int arr[], int *n) {
  int dropped[*n], dLen = 0;
  int i = 1;
  while (i < *n) {
    if (arr[i] < arr[i-1]) {
      dropped[dLen++] = arr[i];
      // shift arr left
      (*n)--;
    } else i++;
  }
  // Sort dropped, merge back
}