Method SortInternal

cpp/src/arrow/compute/kernels/vector_sort.cc:675–743

  }

  Status SortInternal() {
    // Sort each batch independently and merge to sorted indices.
    const int64_t num_batches = static_cast<int64_t>(batches_.size());
    if (num_batches == 0) {
      return Status::OK();
    }
    std::vector<NullPartitionResult> sorted(num_batches);

    // First sort all individual batches
    int64_t begin_offset = 0;
    int64_t end_offset = 0;
    int64_t null_count = 0;
    for (int64_t i = 0; i < num_batches; ++i) {
      const auto& batch = *batches_[i];
      end_offset += batch.num_rows();
      RadixRecordBatchSorter sorter(indices_begin_ + begin_offset,
                                    indices_begin_ + end_offset, batch, options_);
      ARROW_ASSIGN_OR_RAISE(sorted[i], sorter.Sort(begin_offset));
      DCHECK_EQ(sorted[i].overall_begin(), indices_begin_ + begin_offset);
      DCHECK_EQ(sorted[i].overall_end(), indices_begin_ + end_offset);
      DCHECK_EQ(sorted[i].non_null_count() + sorted[i].null_count(), batch.num_rows());
      begin_offset = end_offset;
      // XXX this is an upper bound on the true null count
      null_count += sorted[i].null_count();
    }
    DCHECK_EQ(end_offset, indices_end_ - indices_begin_);

    // Then merge them by pairs, recursively
    if (sorted.size() > 1) {
      ChunkedIndexMapper chunked_mapper(batches_, indices_begin_, indices_end_);
      ARROW_ASSIGN_OR_RAISE(auto chunked_indices_pair,
                            chunked_mapper.LogicalToPhysical());
      auto [chunked_indices_begin, chunked_indices_end] = chunked_indices_pair;

      std::vector<ChunkedNullPartitionResult> chunk_sorted(num_batches);
      for (int64_t i = 0; i < num_batches; ++i) {
        chunk_sorted[i] = sorted[i].TranslateTo(indices_begin_, chunked_indices_begin);
      }

      struct Visitor {
        TableSorter* sorter;
        std::vector<ChunkedNullPartitionResult>* chunk_sorted;
        int64_t null_count;

#define VISIT(TYPE)                                               \
  Status Visit(const TYPE& type) {                                \
    return sorter->MergeInternal<TYPE>(chunk_sorted, null_count); \
  }

        VISIT_SORTABLE_PHYSICAL_TYPES(VISIT)
        VISIT(NullType)
#undef VISIT

        Status Visit(const DataType& type) {
          return Status::NotImplemented("Unsupported type for sorting: ",
                                        type.ToString());
        }
      };