Поиск канонической формы слова (относится к mergeSort, java)

Question

Я застрял в создании канонической формы слова (каноническая форма слова содержит те же буквы, что и исходное слово, но в отсортированном порядке. Например, каноническая форма "компьютер" - это "cemoprtu" (рассмотрим их алфавитный порядок), что из "программы" это "agmoprr".)

Я использую mergeSort для сортировки букв слова, используя следующий код. Все же это только дает мне оригинальное слово вместо канонической формы. Может кто-нибудь сказать мне, что не так с моим кодом?

public static String canonicalForm(String word) {
    char[] string = new char[word.length()];
    for (int i = 0; i < word.length(); i ++) {
        string[i] = word.charAt(i);
    }
    mergeSort(string);
    String result = "";
    for (char ch: string) {
        result += ch;
    }
    System.out.println(result);
}

public static void mergeSort(char[] string) {
    if (string.length > 1) {
        char[] left = Arrays.copyOfRange(string, 0, string.length/2);
        char[] right = Arrays.copyOfRange(string, string.length/2, string.length);
        mergeSort(left);
        mergeSort(right);
        merge(string, left, right);
    }
}

public static void merge(char[] string, char[] left, char[] right) {
    int i1 = 0;
    int i2 = 0;
    for (int i = 0; i < string.length; i ++) {
        if (i1 < left.length) {
            if (left[i1] - right[i2] <= 0) {
                string[i] = left[i1];
                i1 ++;
            }
        } else if (i2 >= right.length) {
            string[i] = left[i1];
            i1 ++;
        } else {
            string[i] = right[i2];
            i2 ++;
        }
    }
}
}

Answer 1

Недостаток в том, что ваше слияние не копирует символы из правой части, если слева [i1] - справа [i2]> 0.

Это работает:

public static void merge(char[] string, char[] left, char[] right) {
    int i1 = 0;
    int i2 = 0;
    for (int i = 0; i < string.length; i++) {
        if (i1 < left.length && i2 < right.length) {
            if (left[i1] - right[i2] <= 0) {
                string[i] = left[i1];
                i1++;
            } else {
                string[i] = right[i2];
                i2++;
            }
        } else if (i2 >= right.length) {
            string[i] = left[i1];
            i1++;
        } else {
            string[i] = right[i2];
            i2++;
        }
    }
}

У вас есть три случая:

1. Символы доступны в обеих частях. Возьмите один с наименьшим значением.
2. Символы доступны только в левой части. Скопируйте их.
3. Символы доступны только в правой части. Скопируйте их.

Answer 2

Я не уверен, почему Вы заново изобретаете колесо, но это можно написать без специальной реализации сортировки, объединения строк и т. Д.

public static String canonicalForm(final String word) {
    final char[] string = word.toCharArray();
    Arrays.sort(string);
    final String result = new String(string);
    System.out.println(result);
    return result;
}