归并排序 | #字符串排序#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        scanner.useDelimiter("\n");
        while (scanner.hasNext()){
            String S = scanner.next();
            int length = 0;
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < S.length(); i++) {
                char c = S.charAt(i);
                if (Character.isLetter(c)) {
                    builder.append(c);
                }
            }
            char[] chars = builder.toString().toCharArray();
            sort(chars, 0, chars.length-1);

            for (int i = 0,j=0; i < S.length(); i++) {
                char c = S.charAt(i);
                if (Character.isLetter(c)) {
                    System.out.print(chars[j++]);
                } else {
                    System.out.print(c);
                }
            }
        }

    }
    public static void sort(char[] chars, int left, int right) {
        if (left>=right) return;
        int mid = left+((right-left)>>1);
        sort(chars, left, mid);
        sort(chars, mid+1, right);
        merge(chars, left, mid, right);
    }

    public static void merge(char[] chars, int left, int mid, int right) {
        char[] copy = new char[chars.length];
        System.arraycopy(chars, left, copy, left, right-left+1);
        
        int k = left,i = left, j = mid + 1;
        while (k<=right) {
            if (i>mid) {
                chars[k++]=copy[j++];
            } else if (j>right) {
                chars[k++]=copy[i++];
            } else if (Character.toLowerCase(copy[i])>Character.toLowerCase(copy[j])) {
                chars[k++]=copy[j++];
            } else if (Character.toLowerCase(copy[i])<=Character.toLowerCase(copy[j]))  {
                chars[k++]=copy[i++];
            }
        }
    }
}