naturalOrdering.scala

import scala.util.Try

/**
 * Адаптированная версия c https://rosettacode.org/wiki/Natural_sorting#Scala
 */
object NaturalOrdering extends Ordering[String] {
  
  def compare(a: String, b: String): Int = {
    val aNumTry = Try(BigDecimal(a))
    val bNumTry = Try(BigDecimal(b))
    
    val numbersCompared = 
      for { aNum <- aNumTry; bNum <- bNumTry }
        yield aNum.compare(bNum)
    
    numbersCompared
      .getOrElse {
        compareNormalized(normalize(a), normalize(b))
      }
  }
  
  private val INT = "([0-9]+)".r
  
  private def compareNormalized(a: Array[String], b: Array[String]) = {
    val l = Math.min(a.length, b.length)
    (0 until l).prefixLength(i => a(i) equals b(i)) match {
      case i if i == l => Math.signum(b.length - a.length).toInt
      case i => (a(i), b(i)) match {
        case (INT(c), INT(d)) => Math.signum(c.toInt - d.toInt).toInt
        case (c, d) => c compareTo d
      }
    }
  }

  private def normalize(s: String) = {
    val replacements = Map('\u00df' -> "ss", '\u017f' -> "s", '\u0292' -> "s").withDefault(s => s.toString) // 8
    import java.text.Normalizer
    Normalizer.normalize(Normalizer.normalize(
      s.trim.toLowerCase, // 1.1, 1.2, 3
      Normalizer.Form.NFKC), // 7
      Normalizer.Form.NFD).replaceAll("[\\p{InCombiningDiacriticalMarks}]", "") // 6
      .replaceAll("^(the|a|an) ", "") // 5
      .flatMap(replacements.apply) // 8
      .split(s"\\s+|(?=[0-9])(?<=[^0-9])|(?=[^0-9])(?<=[0-9])") // 1.3, 2 and 4
  }
}


val input = List(
  "abc", "cba", "bca", "bca 10", "bca 2",
  "4", "5", "5 Super", "3", "10"
)
  
input.sorted.foreach(println)
println()
input.sorted(NaturalOrdering).foreach(println)