| 79 | private: |
| 80 | template <typename Type> |
| 81 | Status SortInternal() { |
| 82 | using ArrayType = typename TypeTraits<Type>::ArrayType; |
| 83 | ArraySortOptions options(order_, null_placement_); |
| 84 | const auto num_chunks = static_cast<int>(physical_chunks_.size()); |
| 85 | if (num_chunks == 0) { |
| 86 | DCHECK_EQ(static_cast<int64_t>(indices_.size()), 0); |
| 87 | *output_ = NullLikePartition::FromCounts(indices_, 0, 0, 0, null_placement_); |
| 88 | return Status::OK(); |
| 89 | } |
| 90 | const int64_t num_indices = static_cast<int64_t>(indices_.size()); |
| 91 | const auto arrays = GetArrayPointers(physical_chunks_); |
| 92 | |
| 93 | // Sort each chunk independently and merge to sorted indices. |
| 94 | // This is a serial implementation. |
| 95 | std::vector<NullLikePartition> sorted(num_chunks); |
| 96 | |
| 97 | // First sort all individual chunks |
| 98 | int64_t begin_offset = 0; |
| 99 | int64_t non_null_like_count = 0; |
| 100 | for (int i = 0; i < num_chunks; ++i) { |
| 101 | const auto array = checked_cast<const ArrayType*>(arrays[i]); |
| 102 | const auto array_length = array->length(); |
| 103 | ARROW_ASSIGN_OR_RAISE( |
| 104 | sorted[i], array_sorter_(indices_.subspan(begin_offset, array_length), *array, |
| 105 | begin_offset, options, ctx_)); |
| 106 | non_null_like_count += sorted[i].non_null_like_range.size(); |
| 107 | begin_offset += array_length; |
| 108 | } |
| 109 | DCHECK_EQ(begin_offset, num_indices); |
| 110 | |
| 111 | // Then merge them by pairs, recursively |
| 112 | if (sorted.size() > 1) { |
| 113 | ChunkedIndexMapper chunked_mapper(arrays, indices_); |
| 114 | ARROW_ASSIGN_OR_RAISE(auto chunked_indices, chunked_mapper.LogicalToPhysical()); |
| 115 | |
| 116 | std::vector<ChunkedNullLikePartition> chunk_sorted(num_chunks); |
| 117 | for (int i = 0; i < num_chunks; ++i) { |
| 118 | chunk_sorted[i] = sorted[i].TranslateTo(indices_, chunked_indices); |
| 119 | } |
| 120 | |
| 121 | // merge function for merging ranges where the first sort key is equal |
| 122 | // -> no-op because we have only one sort key |
| 123 | auto merge_remaining_sort_keys = [&](std::span<CompressedChunkLocation> range, |
| 124 | size_t middle, |
| 125 | CompressedChunkLocation* temp_indices) {}; |
| 126 | |
| 127 | auto merge_non_nulls = [&](std::span<CompressedChunkLocation> range, size_t middle, |
| 128 | CompressedChunkLocation* temp_indices) { |
| 129 | MergeNonNulls<ArrayType>(range.subspan(0, middle), range.subspan(middle), arrays, |
| 130 | {temp_indices, range.size()}); |
| 131 | }; |
| 132 | |
| 133 | ChunkedMergeImpl merge_impl{null_placement_, std::move(merge_remaining_sort_keys), |
| 134 | std::move(merge_non_nulls)}; |
| 135 | // std::merge is only called on non-null-like values, so size temp indices |
| 136 | // accordingly |
| 137 | RETURN_NOT_OK(merge_impl.Init(ctx_, non_null_like_count)); |
| 138 |
nothing calls this directly
no test coverage detected