Method MergeInternal

cpp/src/arrow/compute/kernels/vector_sort.cc:739–773

  // Recursive merge routine, typed on the first sort key
  template <typename ArrowType>
  Status MergeInternal(std::vector<ChunkedNullPartitionResult>* sorted,
                       int64_t null_count) {
    auto merge_nulls = [&](CompressedChunkLocation* nulls_begin,
                           CompressedChunkLocation* nulls_middle,
                           CompressedChunkLocation* nulls_end,
                           CompressedChunkLocation* temp_indices, int64_t null_count) {
      MergeNulls<ArrowType>(nulls_begin, nulls_middle, nulls_end, temp_indices,
                            null_count);
    };
    auto merge_non_nulls =
        [&](CompressedChunkLocation* range_begin, CompressedChunkLocation* range_middle,
            CompressedChunkLocation* range_end, CompressedChunkLocation* temp_indices) {
          MergeNonNulls<ArrowType>(range_begin, range_middle, range_end, temp_indices);
        };

    ChunkedMergeImpl merge_impl(sort_keys_[0].null_placement, std::move(merge_nulls),
                                std::move(merge_non_nulls));
    RETURN_NOT_OK(merge_impl.Init(ctx_, table_.num_rows()));

    while (sorted->size() > 1) {
      auto out_it = sorted->begin();
      auto it = sorted->begin();
      while (it < sorted->end() - 1) {
        const auto& left = *it++;
        const auto& right = *it++;
        DCHECK_EQ(left.overall_end(), right.overall_begin());
        *out_it++ = merge_impl.Merge(left, right, null_count);
      }
      if (it < sorted->end()) {
        *out_it++ = *it++;
      }
      sorted->erase(out_it, sorted->end());
    }
    return comparator_.status();
  }

  template <typename ArrowType>
  void MergeNulls(CompressedChunkLocation* nulls_begin,