package sort

import "k8s.io/apimachinery/pkg/util/sort"

Index ¶

• func MergePreservingRelativeOrder(inputLists [][]string) []string

Functions ¶

func MergePreservingRelativeOrder ¶

func MergePreservingRelativeOrder(inputLists [][]string) []string

MergePreservingRelativeOrder performs a topological consensus sort of items from multiple sources. It merges multiple lists of strings into a single list, preserving the relative order of elements within each source list.

For any two items, if one appears before the other in any of the input lists, that relative order will be preserved in the output. If no relative ordering is defined between two items, they are sorted lexicographically.

The function uses Kahn's algorithm for topological sorting with a min-heap to ensure deterministic output. Items with no dependencies are processed in lexicographic order, guaranteeing consistent results across multiple invocations with the same input.

This function contains a shortcut optimization that returns an input list directly if it already contains all unique items. This provides O(n) performance in the best case.

Example:

• Input: {{"a", "b", "c"}, {"b", "c"}} returns {"a", "b", "c"}
• Input: {{"a", "c"}, {"b", "c"}} returns {"a", "b", "c"} (lexicographic tie-breaking)
• Input: {{"a", "b"}, {"b", "a"}} returns error (cycle detected)

Complexity: O(L*n + V*log(V) + E) where L is the number of lists, n is the average list size, V is the number of unique items, and E is the number of precedence edges.

This is useful for creating a stable, consistent ordering when merging data from multiple sources that may have partial but not conflicting orderings.

Source Files ¶

sort.go