diff --git a/android/apex.go b/android/apex.go
index 3c945ae..358818f 100644
--- a/android/apex.go
+++ b/android/apex.go
@@ -817,7 +817,7 @@
 	var flatContent strings.Builder
 
 	fmt.Fprintf(&fullContent, "%s(minSdkVersion:%s):\n", ctx.ModuleName(), minSdkVersion)
-	for _, key := range FirstUniqueStrings(SortedStringKeys(depInfos)) {
+	for _, key := range FirstUniqueStrings(SortedKeys(depInfos)) {
 		info := depInfos[key]
 		toName := fmt.Sprintf("%s(minSdkVersion:%s)", info.To, info.MinSdkVersion)
 		if info.IsExternal {
diff --git a/android/defaults.go b/android/defaults.go
index 925eafc..a821b28 100644
--- a/android/defaults.go
+++ b/android/defaults.go
@@ -302,7 +302,7 @@
 			delete(propertiesSet, "visibility")
 
 			// Replace the "*" with the names of all the properties that have been set.
-			protectedProperties = SortedStringKeys(propertiesSet)
+			protectedProperties = SortedKeys(propertiesSet)
 			module.setProtectedProperties(protectedProperties)
 		} else {
 			for _, property := range protectedProperties {
diff --git a/android/module.go b/android/module.go
index 97c9706..58c5464 100644
--- a/android/module.go
+++ b/android/module.go
@@ -3675,7 +3675,7 @@
 	// Ensure ancestor directories are in dirMap
 	// Make directories build their direct subdirectories
 	// Returns a slice of all directories and a slice of top-level directories.
-	dirs := SortedStringKeys(dirMap)
+	dirs := SortedKeys(dirMap)
 	for _, dir := range dirs {
 		dir := parentDir(dir)
 		for dir != "." && dir != "/" {
@@ -3686,7 +3686,7 @@
 			dir = parentDir(dir)
 		}
 	}
-	dirs = SortedStringKeys(dirMap)
+	dirs = SortedKeys(dirMap)
 	var topDirs []string
 	for _, dir := range dirs {
 		p := parentDir(dir)
@@ -3696,7 +3696,7 @@
 			topDirs = append(topDirs, dir)
 		}
 	}
-	return SortedStringKeys(dirMap), topDirs
+	return SortedKeys(dirMap), topDirs
 }
 
 func (c *buildTargetSingleton) GenerateBuildActions(ctx SingletonContext) {
@@ -3782,7 +3782,7 @@
 	}
 
 	// Wrap those into host|host-cross|target phony rules
-	for _, class := range SortedStringKeys(osClass) {
+	for _, class := range SortedKeys(osClass) {
 		ctx.Phony(class, osClass[class]...)
 	}
 }
diff --git a/android/neverallow.go b/android/neverallow.go
index ad9880a..ba5385c 100644
--- a/android/neverallow.go
+++ b/android/neverallow.go
@@ -542,7 +542,7 @@
 		s = append(s, fmt.Sprintf("properties matching: %s", r.props))
 	}
 	if len(r.directDeps) > 0 {
-		s = append(s, fmt.Sprintf("dep(s): %q", SortedStringKeys(r.directDeps)))
+		s = append(s, fmt.Sprintf("dep(s): %q", SortedKeys(r.directDeps)))
 	}
 	if len(r.osClasses) > 0 {
 		s = append(s, fmt.Sprintf("os class(es): %q", r.osClasses))
diff --git a/android/packaging.go b/android/packaging.go
index ecd84a2..4a9b591 100644
--- a/android/packaging.go
+++ b/android/packaging.go
@@ -240,7 +240,7 @@
 // entries into the specified directory.
 func (p *PackagingBase) CopySpecsToDir(ctx ModuleContext, builder *RuleBuilder, specs map[string]PackagingSpec, dir ModuleOutPath) (entries []string) {
 	seenDir := make(map[string]bool)
-	for _, k := range SortedStringKeys(specs) {
+	for _, k := range SortedKeys(specs) {
 		ps := specs[k]
 		destPath := dir.Join(ctx, ps.relPathInPackage).String()
 		destDir := filepath.Dir(destPath)
diff --git a/android/phony.go b/android/phony.go
index 0adbb55..814a9e3 100644
--- a/android/phony.go
+++ b/android/phony.go
@@ -48,7 +48,7 @@
 
 func (p *phonySingleton) GenerateBuildActions(ctx SingletonContext) {
 	p.phonyMap = getPhonyMap(ctx.Config())
-	p.phonyList = SortedStringKeys(p.phonyMap)
+	p.phonyList = SortedKeys(p.phonyMap)
 	for _, phony := range p.phonyList {
 		p.phonyMap[phony] = SortedUniquePaths(p.phonyMap[phony])
 	}
diff --git a/android/soongconfig/modules.go b/android/soongconfig/modules.go
index ed4888d..9239ca9 100644
--- a/android/soongconfig/modules.go
+++ b/android/soongconfig/modules.go
@@ -301,23 +301,6 @@
 	}
 }
 
-// This is a copy of the one available in soong/android/util.go, but depending
-// on the android package causes a cyclic dependency. A refactoring here is to
-// extract common utils out from android/utils.go for other packages like this.
-func sortedStringKeys(m interface{}) []string {
-	v := reflect.ValueOf(m)
-	if v.Kind() != reflect.Map {
-		panic(fmt.Sprintf("%#v is not a map", m))
-	}
-	keys := v.MapKeys()
-	s := make([]string, 0, len(keys))
-	for _, key := range keys {
-		s = append(s, key.String())
-	}
-	sort.Strings(s)
-	return s
-}
-
 // String emits the Soong config variable definitions as Starlark dictionaries.
 func (defs Bp2BuildSoongConfigDefinitions) String() string {
 	ret := ""
diff --git a/android/test_suites.go b/android/test_suites.go
index 55e1da7..b570b23 100644
--- a/android/test_suites.go
+++ b/android/test_suites.go
@@ -57,7 +57,7 @@
 
 func robolectricTestSuite(ctx SingletonContext, files map[string]InstallPaths) WritablePath {
 	var installedPaths InstallPaths
-	for _, module := range SortedStringKeys(files) {
+	for _, module := range SortedKeys(files) {
 		installedPaths = append(installedPaths, files[module]...)
 	}
 	testCasesDir := pathForInstall(ctx, ctx.Config().BuildOS, X86, "testcases", false)
diff --git a/android/util.go b/android/util.go
index 8f4c17d..6c0ddf4 100644
--- a/android/util.go
+++ b/android/util.go
@@ -62,25 +62,9 @@
 	return buf.String()
 }
 
-// JoinWithSuffix appends the suffix to each string in the list and
-// returns them joined together with given separator.
-func JoinWithSuffix(strs []string, suffix string, separator string) string {
-	if len(strs) == 0 {
-		return ""
-	}
-
-	var buf strings.Builder
-	buf.WriteString(strs[0])
-	buf.WriteString(suffix)
-	for i := 1; i < len(strs); i++ {
-		buf.WriteString(separator)
-		buf.WriteString(strs[i])
-		buf.WriteString(suffix)
-	}
-	return buf.String()
-}
-
-// SorterStringKeys returns the keys of the given string-keyed map in the ascending order.
+// SortedStringKeys returns the keys of the given map in the ascending order.
+//
+// Deprecated: Use SortedKeys instead.
 func SortedStringKeys(m interface{}) []string {
 	v := reflect.ValueOf(m)
 	if v.Kind() != reflect.Map {
@@ -98,6 +82,28 @@
 	return s
 }
 
+type Ordered interface {
+	~string |
+		~float32 | ~float64 |
+		~int | ~int8 | ~int16 | ~int32 | ~int64 |
+		~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 | ~uintptr
+}
+
+// SortedKeys returns the keys of the given map in the ascending order.
+func SortedKeys[T Ordered, V any](m map[T]V) []T {
+	if len(m) == 0 {
+		return nil
+	}
+	ret := make([]T, 0, len(m))
+	for k := range m {
+		ret = append(ret, k)
+	}
+	sort.Slice(ret, func(i, j int) bool {
+		return ret[i] < ret[j]
+	})
+	return ret
+}
+
 // stringValues returns the values of the given string-valued map in randomized map order.
 func stringValues(m interface{}) []string {
 	v := reflect.ValueOf(m)
diff --git a/android/util_test.go b/android/util_test.go
index 9b9253b..51d8e32 100644
--- a/android/util_test.go
+++ b/android/util_test.go
@@ -641,6 +641,36 @@
 	}
 }
 
+func testSortedKeysHelper[K Ordered, V any](t *testing.T, name string, input map[K]V, expected []K) {
+	t.Helper()
+	t.Run(name, func(t *testing.T) {
+		actual := SortedKeys(input)
+		if !reflect.DeepEqual(actual, expected) {
+			t.Errorf("expected %q, got %q", expected, actual)
+		}
+	})
+}
+
+func TestSortedKeys(t *testing.T) {
+	testSortedKeysHelper(t, "simple", map[string]string{
+		"b": "bar",
+		"a": "foo",
+	}, []string{
+		"a",
+		"b",
+	})
+	testSortedKeysHelper(t, "ints", map[int]interface{}{
+		10: nil,
+		5:  nil,
+	}, []int{
+		5,
+		10,
+	})
+
+	testSortedKeysHelper(t, "nil", map[string]string(nil), nil)
+	testSortedKeysHelper(t, "empty", map[string]string{}, nil)
+}
+
 func TestSortedStringKeys(t *testing.T) {
 	testCases := []struct {
 		name     string