diff --git a/src/com/android/providers/contacts/ContactLocaleUtils.java b/src/com/android/providers/contacts/ContactLocaleUtils.java
index 0e7b292..0284c01 100644
--- a/src/com/android/providers/contacts/ContactLocaleUtils.java
+++ b/src/com/android/providers/contacts/ContactLocaleUtils.java
@@ -17,78 +17,263 @@
 package com.android.providers.contacts;
 
 import android.provider.ContactsContract.FullNameStyle;
-import android.util.SparseArray;
+import android.util.Log;
 
 import com.android.providers.contacts.HanziToPinyin.Token;
 
+import java.lang.Character.UnicodeBlock;
+import java.util.Arrays;
 import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
+import java.util.List;
 import java.util.Locale;
+import java.util.Map;
+import java.util.Set;
+
+import libcore.icu.AlphabeticIndex;
 
 /**
- * This utility class provides customized sort key and name lookup key according the locale.
+ * This utility class provides specialized handling for locale specific
+ * information: labels, name lookup keys.
  */
 public class ContactLocaleUtils {
+    public static final String TAG = "ContactLocale";
 
     /**
-     * This class is the default implementation.
-     * <p>
-     * It should be the base class for other locales' implementation.
+     * This class is the default implementation and should be the base class
+     * for other locales.
+     *
+     * sortKey: same as name
+     * nameLookupKeys: none
+     * labels: uses ICU AlphabeticIndex for labels and extends by labeling
+     *     phone numbers "#".  Eg English labels are: [A-Z], #, " "
      */
-    public class ContactLocaleUtilsBase {
-        public String getSortKey(String displayName) {
-            return displayName;
+    private static class ContactLocaleUtilsBase {
+        private static final String EMPTY_STRING = "";
+        private static final String NUMBER_STRING = "#";
+
+        protected final AlphabeticIndex mAlphabeticIndex;
+        private final int mAlphabeticIndexBucketCount;
+        private final int mNumberBucketIndex;
+
+        public ContactLocaleUtilsBase(Locale locale) {
+            mAlphabeticIndex = new AlphabeticIndex(locale);
+            mAlphabeticIndex.addLabels(Locale.US);
+            // Force creation of lazy-init data structures.
+            mAlphabeticIndexBucketCount = mAlphabeticIndex.getBucketCount();
+            mNumberBucketIndex = mAlphabeticIndexBucketCount - 1;
         }
+
+        public String getSortKey(String name) {
+            return name;
+        }
+
+        /**
+         * Returns the bucket index for the specified string. AlphabeticIndex
+         * sorts strings into buckets numbered in order from 0 to N, where the
+         * exact value of N depends on how many representative index labels are
+         * used in a particular locale. This routine adds one additional bucket
+         * for phone numbers. It attempts to detect phone numbers and shifts
+         * the bucket indexes returned by AlphabeticIndex in order to make room
+         * for the new # bucket, so the returned range becomes 0 to N+1.
+         */
+        public int getBucketIndex(String name) {
+            boolean prefixIsNumeric = false;
+            final int length = name.length();
+            int offset = 0;
+            while (offset < length) {
+                int codePoint = Character.codePointAt(name, offset);
+                // Ignore standard phone number separators and identify any
+                // string that otherwise starts with a number.
+                if (Character.isDigit(codePoint)) {
+                    prefixIsNumeric = true;
+                    break;
+                } else if (!Character.isSpaceChar(codePoint) &&
+                           codePoint != '+' && codePoint != '(' &&
+                           codePoint != ')' && codePoint != '.' &&
+                           codePoint != '-' && codePoint != '#') {
+                    break;
+                }
+                offset += Character.charCount(codePoint);
+            }
+            if (prefixIsNumeric) {
+                return mNumberBucketIndex;
+            }
+
+            final int bucket = mAlphabeticIndex.getBucketIndex(name);
+            if (bucket < 0) {
+                return -1;
+            }
+            if (bucket >= mNumberBucketIndex) {
+                return bucket + 1;
+            }
+            return bucket;
+        }
+
+        /**
+         * Returns the number of buckets in use (one more than AlphabeticIndex
+         * uses, because this class adds a bucket for phone numbers).
+         */
+        public int getBucketCount() {
+            return mAlphabeticIndexBucketCount + 1;
+        }
+
+        /**
+         * Returns the label for the specified bucket index if a valid index,
+         * otherwise returns an empty string. '#' is returned for the phone
+         * number bucket; for all others, the AlphabeticIndex label is returned.
+         */
+        public String getBucketLabel(int bucketIndex) {
+            if (bucketIndex < 0 || bucketIndex >= getBucketCount()) {
+                return EMPTY_STRING;
+            } else if (bucketIndex == mNumberBucketIndex) {
+                return NUMBER_STRING;
+            } else if (bucketIndex > mNumberBucketIndex) {
+                --bucketIndex;
+            }
+            return mAlphabeticIndex.getBucketLabel(bucketIndex);
+        }
+
         @SuppressWarnings("unused")
         public Iterator<String> getNameLookupKeys(String name) {
             return null;
         }
+
+        public ArrayList<String> getLabels() {
+            final int bucketCount = getBucketCount();
+            final ArrayList<String> labels = new ArrayList<String>(bucketCount);
+            for(int i = 0; i < bucketCount; ++i) {
+                labels.add(getBucketLabel(i));
+            }
+            return labels;
+        }
     }
 
     /**
-     * The classes to generate the Chinese style sort and search keys.
-     * <p>
-     * The sorting key is generated as each Chinese character' pinyin proceeding with
-     * space and character itself. If the character's pinyin unable to find, the character
-     * itself will be used.
-     * <p>
-     * The below additional name lookup keys will be generated.
-     * a. Chinese character's pinyin and pinyin's initial character.
-     * b. Latin word and the initial character for Latin word.
-     * The name lookup keys are generated to make sure the name can be found by from any
-     * initial character.
+     * Japanese specific locale overrides.
+     *
+     * sortKey: unchanged (same as name)
+     * nameLookupKeys: unchanged (none)
+     * labels: extends default labels by labeling unlabeled CJ characters
+     *     with the Japanese character 他 ("misc"). Japanese labels are:
+     *     あ, か, さ, た, な, は, ま, や, ら, わ, 他, [A-Z], #, " "
      */
-    private class ChineseContactUtils extends ContactLocaleUtilsBase {
+    private static class JapaneseContactUtils extends ContactLocaleUtilsBase {
+        // \u4ed6 is Japanese character 他 ("misc")
+        private static final String JAPANESE_MISC_LABEL = "\u4ed6";
+        private final int mMiscBucketIndex;
+
+        public JapaneseContactUtils(Locale locale) {
+            super(locale);
+            // Determine which bucket AlphabeticIndex is lumping unclassified
+            // Japanese characters into by looking up the bucket index for
+            // a representative Kanji/CJK unified ideograph (\u65e5 is the
+            // character '日').
+            mMiscBucketIndex = super.getBucketIndex("\u65e5");
+        }
+
+        // Set of UnicodeBlocks for unified CJK (Chinese) characters and
+        // Japanese characters. This includes all code blocks that might
+        // contain a character used in Japanese (which is why unified CJK
+        // blocks are included but Korean Hangul and jamo are not).
+        private static final Set<Character.UnicodeBlock> CJ_BLOCKS;
+        static {
+            Set<UnicodeBlock> set = new HashSet<UnicodeBlock>();
+            set.add(UnicodeBlock.HIRAGANA);
+            set.add(UnicodeBlock.KATAKANA);
+            set.add(UnicodeBlock.KATAKANA_PHONETIC_EXTENSIONS);
+            set.add(UnicodeBlock.HALFWIDTH_AND_FULLWIDTH_FORMS);
+            set.add(UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS);
+            set.add(UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS_EXTENSION_A);
+            set.add(UnicodeBlock.CJK_UNIFIED_IDEOGRAPHS_EXTENSION_B);
+            set.add(UnicodeBlock.CJK_SYMBOLS_AND_PUNCTUATION);
+            set.add(UnicodeBlock.CJK_RADICALS_SUPPLEMENT);
+            set.add(UnicodeBlock.CJK_COMPATIBILITY);
+            set.add(UnicodeBlock.CJK_COMPATIBILITY_FORMS);
+            set.add(UnicodeBlock.CJK_COMPATIBILITY_IDEOGRAPHS);
+            set.add(UnicodeBlock.CJK_COMPATIBILITY_IDEOGRAPHS_SUPPLEMENT);
+            CJ_BLOCKS = Collections.unmodifiableSet(set);
+        }
+
+        /**
+         * Helper routine to identify unlabeled Chinese or Japanese characters
+         * to put in a 'misc' bucket.
+         *
+         * @return true if the specified Unicode code point is Chinese or
+         *              Japanese
+         */
+        private static boolean isChineseOrJapanese(int codePoint) {
+            return CJ_BLOCKS.contains(UnicodeBlock.of(codePoint));
+        }
+
+        /**
+         * Returns the bucket index for the specified string. Adds an
+         * additional 'misc' bucket for Kanji characters to the base class set.
+         */
         @Override
-        public String getSortKey(String displayName) {
-            ArrayList<Token> tokens = HanziToPinyin.getInstance().get(displayName);
-            if (tokens != null && tokens.size() > 0) {
-                StringBuilder sb = new StringBuilder();
-                for (Token token : tokens) {
-                    // Put Chinese character's pinyin, then proceed with the
-                    // character itself.
-                    if (Token.PINYIN == token.type) {
-                        if (sb.length() > 0) {
-                            sb.append(' ');
-                        }
-                        sb.append(token.target);
-                        sb.append(' ');
-                        sb.append(token.source);
-                    } else {
-                        if (sb.length() > 0) {
-                            sb.append(' ');
-                        }
-                        sb.append(token.source);
-                    }
-                }
-                return sb.toString();
+        public int getBucketIndex(String name) {
+            final int bucketIndex = super.getBucketIndex(name);
+            if ((bucketIndex == mMiscBucketIndex &&
+                 !isChineseOrJapanese(Character.codePointAt(name, 0))) ||
+                bucketIndex > mMiscBucketIndex) {
+                return bucketIndex + 1;
             }
-            return super.getSortKey(displayName);
+            return bucketIndex;
+        }
+
+        /**
+         * Returns the number of buckets in use (one more than the base class
+         * uses, because this class adds a bucket for Kanji).
+         */
+        @Override
+        public int getBucketCount() {
+            return super.getBucketCount() + 1;
+        }
+
+        /**
+         * Returns the label for the specified bucket index if a valid index,
+         * otherwise returns an empty string. '他' is returned for unclassified
+         * Kanji; for all others, the label determined by the base class is
+         * returned.
+         */
+        @Override
+        public String getBucketLabel(int bucketIndex) {
+            if (bucketIndex == mMiscBucketIndex) {
+                return JAPANESE_MISC_LABEL;
+            } else if (bucketIndex > mMiscBucketIndex) {
+                --bucketIndex;
+            }
+            return super.getBucketLabel(bucketIndex);
+        }
+    }
+
+    /**
+     * Chinese specific locale overrides. Uses ICU Transliterator for
+     * generating pinyin transliteration.
+     *
+     * sortKey: unchanged (same as name)
+     * nameLookupKeys: adds additional name lookup keys
+     *     - Chinese character's pinyin and pinyin's initial character.
+     *     - Latin word and initial character.
+     * labels: unchanged
+     *     Simplified Chinese labels are the same as English: [A-Z], #, " "
+     *     Traditional Chinese labels are stroke count, then English labels:
+     *         [1-18], [A-Z], #, " "
+     */
+    private static class ChineseContactUtils extends ContactLocaleUtilsBase {
+        public ChineseContactUtils(Locale locale) {
+            super(locale);
         }
 
         @Override
         public Iterator<String> getNameLookupKeys(String name) {
+            return getPinyinNameLookupKeys(name);
+        }
+
+        public static Iterator<String> getPinyinNameLookupKeys(String name) {
             // TODO : Reduce the object allocation.
             HashSet<String> keys = new HashSet<String>();
             ArrayList<Token> tokens = HanziToPinyin.getInstance().get(name);
@@ -96,9 +281,9 @@
             final StringBuilder keyPinyin = new StringBuilder();
             final StringBuilder keyInitial = new StringBuilder();
             // There is no space among the Chinese Characters, the variant name
-            // lookup key wouldn't work for Chinese. The keyOrignal is used to
+            // lookup key wouldn't work for Chinese. The keyOriginal is used to
             // build the lookup keys for itself.
-            final StringBuilder keyOrignal = new StringBuilder();
+            final StringBuilder keyOriginal = new StringBuilder();
             for (int i = tokenCount - 1; i >= 0; i--) {
                 final Token token = tokens.get(i);
                 if (Token.PINYIN == token.type) {
@@ -109,14 +294,14 @@
                     if (keyPinyin.length() > 0) {
                         keyPinyin.insert(0, ' ');
                     }
-                    if (keyOrignal.length() > 0) {
-                        keyOrignal.insert(0, ' ');
+                    if (keyOriginal.length() > 0) {
+                        keyOriginal.insert(0, ' ');
                     }
                     keyPinyin.insert(0, token.source);
                     keyInitial.insert(0, token.source.charAt(0));
                 }
-                keyOrignal.insert(0, token.source);
-                keys.add(keyOrignal.toString());
+                keyOriginal.insert(0, token.source);
+                keys.add(keyOriginal.toString());
                 keys.add(keyPinyin.toString());
                 keys.add(keyInitial.toString());
             }
@@ -124,89 +309,147 @@
         }
     }
 
+    /**
+     * Traditional Chinese specific locale overrides. Rewrites ICU labels
+     * to correct ICU 4.9 labels.
+     *
+     * TODO: remove once ICU is upgraded to 5.0 and labels are fixed
+     *
+     * sortKey: unchanged from base class (same as name)
+     * nameLookupKeys: unchanged from ChineseContactUtils
+     * labels: unchanged
+     *     Simplified Chinese labels are the same as English: [A-Z], #, " "
+     *     Traditional Chinese labels are stroke count, then English labels:
+     *         [1-18]劃, [A-Z], #, " "
+     */
+    private static class TraditionalChineseContactUtils
+        extends ChineseContactUtils {
+        // Remap ICU 4.9 labels to desired values
+        private static final Map<String, String> labelMap;
+        static {
+            Map<String, String> map = new HashMap<String, String>();
+            final List<String> oldLabels =
+                Arrays.asList("\u4E00", "\u4E01", "\u4E08", "\u4E0D",
+                              "\u4E14", "\u4E1E", "\u4E32", "\u4E26",
+                              "\u4EAD", "\u4E58", "\u4E7E", "\u5080",
+                              "\u4E82", "\u50CE", "\u50F5", "\u5110",
+                              "\u511F", "\u53E2", "\u5133", "\u56B4",
+                              "\u5137", "\u513B", "\u56CC", "\u56D1",
+                              "\u5EF3");
+            int strokeCount = 1;
+            for(String oldLabel : oldLabels) {
+                String newLabel = "" + strokeCount + "\u5283";
+                map.put(oldLabel, newLabel);
+                ++strokeCount;
+            }
+            labelMap = Collections.unmodifiableMap(map);
+        }
+
+        public TraditionalChineseContactUtils(Locale locale) {
+            super(locale);
+        }
+
+        @Override
+        public String getBucketLabel(int bucketIndex) {
+            final String label = super.getBucketLabel(bucketIndex);
+            final String remappedLabel = labelMap.get(label);
+            return remappedLabel != null ? remappedLabel : label;
+        }
+    }
+
     private static final String CHINESE_LANGUAGE = Locale.CHINESE.getLanguage().toLowerCase();
     private static final String JAPANESE_LANGUAGE = Locale.JAPANESE.getLanguage().toLowerCase();
     private static final String KOREAN_LANGUAGE = Locale.KOREAN.getLanguage().toLowerCase();
 
     private static ContactLocaleUtils sSingleton;
-    private final SparseArray<ContactLocaleUtilsBase> mUtils =
-            new SparseArray<ContactLocaleUtilsBase>();
 
-    private final ContactLocaleUtilsBase mBase = new ContactLocaleUtilsBase();
+    private final Locale mLocale;
+    private final String mLanguage;
+    private final ContactLocaleUtilsBase mUtils;
 
-    private String mLanguage;
-
-    private ContactLocaleUtils() {
-        setLocale(null);
-    }
-
-    public void setLocale(Locale currentLocale) {
-        if (currentLocale == null) {
-            mLanguage = Locale.getDefault().getLanguage().toLowerCase();
+    private ContactLocaleUtils(Locale locale) {
+        if (locale == null) {
+            mLocale = Locale.getDefault();
         } else {
-            mLanguage = currentLocale.getLanguage().toLowerCase();
+            mLocale = locale;
         }
-    }
-
-    public String getSortKey(String displayName, int nameStyle) {
-        return getForSort(Integer.valueOf(nameStyle)).getSortKey(displayName);
-    }
-
-    public Iterator<String> getNameLookupKeys(String name, int nameStyle) {
-        return getForNameLookup(Integer.valueOf(nameStyle)).getNameLookupKeys(name);
-    }
-
-    /**
-     *  Determine which utility should be used for generating NameLookupKey.
-     *  <p>
-     *  a. For Western style name, if the current language is Chinese, the
-     *     ChineseContactUtils should be used.
-     *  b. For Chinese and CJK style name if current language is neither Japanese or Korean,
-     *     the ChineseContactUtils should be used.
-     */
-    private ContactLocaleUtilsBase getForNameLookup(Integer nameStyle) {
-        int nameStyleInt = nameStyle.intValue();
-        Integer adjustedUtil = Integer.valueOf(getAdjustedStyle(nameStyleInt));
-        if (CHINESE_LANGUAGE.equals(mLanguage) && nameStyleInt == FullNameStyle.WESTERN) {
-            adjustedUtil = Integer.valueOf(FullNameStyle.CHINESE);
-        }
-        return get(adjustedUtil);
-    }
-
-    private synchronized ContactLocaleUtilsBase get(Integer nameStyle) {
-        ContactLocaleUtilsBase utils = mUtils.get(nameStyle);
-        if (utils == null) {
-            if (nameStyle.intValue() == FullNameStyle.CHINESE) {
-                utils = new ChineseContactUtils();
-                mUtils.put(nameStyle, utils);
+        mLanguage = mLocale.getLanguage().toLowerCase();
+        if (mLanguage.equals(JAPANESE_LANGUAGE)) {
+            mUtils = new JapaneseContactUtils(mLocale);
+        } else if (mLanguage.equals(CHINESE_LANGUAGE)) {
+            if (isLocale(Locale.TRADITIONAL_CHINESE)) {
+                mUtils = new TraditionalChineseContactUtils(mLocale);
+            } else {
+                mUtils = new ChineseContactUtils(mLocale);
             }
+        } else {
+            mUtils = new ContactLocaleUtilsBase(mLocale);
         }
-        return (utils == null) ? mBase : utils;
+        Log.i(TAG, "AddressBook Labels [" + mLocale.toString() + "]: "
+              + getLabels().toString());
     }
 
-    /**
-     *  Determine the which utility should be used for generating sort key.
-     *  <p>
-     *  For Chinese and CJK style name if current language is neither Japanese or Korean,
-     *  the ChineseContactUtils should be used.
-     */
-    private ContactLocaleUtilsBase getForSort(Integer nameStyle) {
-        return get(Integer.valueOf(getAdjustedStyle(nameStyle.intValue())));
+    public boolean isLocale(Locale locale) {
+        return mLocale.equals(locale);
     }
 
-    public static synchronized ContactLocaleUtils getIntance() {
+    public static synchronized ContactLocaleUtils getInstance() {
         if (sSingleton == null) {
-            sSingleton = new ContactLocaleUtils();
+            sSingleton = new ContactLocaleUtils(null);
         }
         return sSingleton;
     }
 
-    private int getAdjustedStyle(int nameStyle) {
-        if (nameStyle == FullNameStyle.CJK  && !JAPANESE_LANGUAGE.equals(mLanguage) &&
-                !KOREAN_LANGUAGE.equals(mLanguage)) {
-            return FullNameStyle.CHINESE;
-        } else {
-            return nameStyle;
+    public static synchronized void setLocale(Locale locale) {
+        if (sSingleton == null || !sSingleton.isLocale(locale)) {
+            sSingleton = new ContactLocaleUtils(locale);
         }
     }
+
+    public String getSortKey(String name, int nameStyle) {
+        return mUtils.getSortKey(name);
+    }
+
+    public int getBucketIndex(String name) {
+        return mUtils.getBucketIndex(name);
+    }
+
+    public int getBucketCount() {
+        return mUtils.getBucketCount();
+    }
+
+    public String getBucketLabel(int bucketIndex) {
+        return mUtils.getBucketLabel(bucketIndex);
+    }
+
+    public String getLabel(String name) {
+        return getBucketLabel(getBucketIndex(name));
+    }
+
+    public ArrayList<String> getLabels() {
+        return mUtils.getLabels();
+    }
+
+    /**
+     *  Determine which utility should be used for generating NameLookupKey.
+     *  (ie, whether we generate Pinyin lookup keys or not)
+     *
+     *  a. For unclassified CJK name, if current locale language is neither
+     *     Japanese nor Korean, use ChineseContactUtils.
+     *  b. If we're sure this is a Chinese name, always use ChineseContactUtils.
+     *  c. Otherwise, use whichever ContactUtils are appropriate for the locale
+     *     (so, Western names in Chinese locale will use ChineseContactUtils)
+     */
+    public Iterator<String> getNameLookupKeys(String name, int nameStyle) {
+        if (nameStyle == FullNameStyle.CJK &&
+            !JAPANESE_LANGUAGE.equals(mLanguage) &&
+            !KOREAN_LANGUAGE.equals(mLanguage)) {
+            return ChineseContactUtils.getPinyinNameLookupKeys(name);
+        }
+        if (nameStyle == FullNameStyle.CHINESE) {
+            return ChineseContactUtils.getPinyinNameLookupKeys(name);
+        }
+        return mUtils.getNameLookupKeys(name);
+    }
+
 }
diff --git a/src/com/android/providers/contacts/ContactsDatabaseHelper.java b/src/com/android/providers/contacts/ContactsDatabaseHelper.java
index 478cd68..6cd0a70 100644
--- a/src/com/android/providers/contacts/ContactsDatabaseHelper.java
+++ b/src/com/android/providers/contacts/ContactsDatabaseHelper.java
@@ -107,7 +107,7 @@
      *   700-799 Jelly Bean
      * </pre>
      */
-    static final int DATABASE_VERSION = 706;
+    static final int DATABASE_VERSION = 707;
 
     private static final String DATABASE_NAME = "contacts2.db";
     private static final String DATABASE_PRESENCE = "presence_db";
@@ -359,6 +359,10 @@
                 + Contacts.SEND_TO_VOICEMAIL;
         public static final String CONCRETE_LOOKUP_KEY = Tables.CONTACTS + "."
                 + Contacts.LOOKUP_KEY;
+        public static final String PHONEBOOK_LABEL_PRIMARY = "phonebook_label";
+        public static final String PHONEBOOK_BUCKET_PRIMARY = "phonebook_bucket";
+        public static final String PHONEBOOK_LABEL_ALTERNATIVE = "phonebook_label_alt";
+        public static final String PHONEBOOK_BUCKET_ALTERNATIVE = "phonebook_bucket_alt";
     }
 
     public interface RawContactsColumns {
@@ -403,7 +407,15 @@
         public static final String CONCRETE_CONTACT_ID =
                 Tables.RAW_CONTACTS + "." + RawContacts.CONTACT_ID;
         public static final String CONCRETE_NAME_VERIFIED =
-                Tables.RAW_CONTACTS + "." + RawContacts.NAME_VERIFIED;
+            Tables.RAW_CONTACTS + "." + RawContacts.NAME_VERIFIED;
+        public static final String PHONEBOOK_LABEL_PRIMARY =
+            ContactsColumns.PHONEBOOK_LABEL_PRIMARY;
+        public static final String PHONEBOOK_BUCKET_PRIMARY =
+            ContactsColumns.PHONEBOOK_BUCKET_PRIMARY;
+        public static final String PHONEBOOK_LABEL_ALTERNATIVE =
+            ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE;
+        public static final String PHONEBOOK_BUCKET_ALTERNATIVE =
+            ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE;
     }
 
     public interface ViewRawContactsColumns {
@@ -983,8 +995,12 @@
                 RawContacts.PHONETIC_NAME_STYLE + " TEXT," +
                 RawContacts.SORT_KEY_PRIMARY + " TEXT COLLATE " +
                         ContactsProvider2.PHONEBOOK_COLLATOR_NAME + "," +
+                RawContactsColumns.PHONEBOOK_LABEL_PRIMARY + " TEXT," +
+                RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY + " INTEGER," +
                 RawContacts.SORT_KEY_ALTERNATIVE + " TEXT COLLATE " +
                         ContactsProvider2.PHONEBOOK_COLLATOR_NAME + "," +
+                RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE + " TEXT," +
+                RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE + " INTEGER," +
                 RawContacts.NAME_VERIFIED + " INTEGER NOT NULL DEFAULT 0," +
                 RawContacts.SYNC1 + " TEXT, " +
                 RawContacts.SYNC2 + " TEXT, " +
@@ -1612,8 +1628,16 @@
                         + " AS " + Contacts.PHONETIC_NAME_STYLE + ", "
                 + "name_raw_contact." + RawContacts.SORT_KEY_PRIMARY
                         + " AS " + Contacts.SORT_KEY_PRIMARY + ", "
+                + "name_raw_contact." + RawContactsColumns.PHONEBOOK_LABEL_PRIMARY
+                        + " AS " + ContactsColumns.PHONEBOOK_LABEL_PRIMARY + ", "
+                + "name_raw_contact." + RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY
+                        + " AS " + ContactsColumns.PHONEBOOK_BUCKET_PRIMARY + ", "
                 + "name_raw_contact." + RawContacts.SORT_KEY_ALTERNATIVE
-                        + " AS " + Contacts.SORT_KEY_ALTERNATIVE;
+                        + " AS " + Contacts.SORT_KEY_ALTERNATIVE + ", "
+                + "name_raw_contact." + RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE
+                        + " AS " + ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE + ", "
+                + "name_raw_contact." + RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE
+                        + " AS " + ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE;
 
         String dataSelect = "SELECT "
                 + DataColumns.CONCRETE_ID + " AS " + Data._ID + ","
@@ -1670,7 +1694,11 @@
                 + RawContacts.PHONETIC_NAME  + ", "
                 + RawContacts.PHONETIC_NAME_STYLE  + ", "
                 + RawContacts.SORT_KEY_PRIMARY  + ", "
+                + RawContactsColumns.PHONEBOOK_LABEL_PRIMARY  + ", "
+                + RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY  + ", "
                 + RawContacts.SORT_KEY_ALTERNATIVE + ", "
+                + RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE  + ", "
+                + RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE  + ", "
                 + dbForProfile() + " AS " + RawContacts.RAW_CONTACT_IS_USER_PROFILE + ", "
                 + rawContactOptionColumns + ", "
                 + syncColumns
@@ -2408,6 +2436,12 @@
             oldVersion = 706;
         }
 
+        if (oldVersion < 707) {
+            upgradeToVersion707(db);
+            upgradeViewsAndTriggers = true;
+            oldVersion = 707;
+        }
+
         if (upgradeViewsAndTriggers) {
             createContactsViews(db);
             createGroupsView(db);
@@ -2718,8 +2752,7 @@
                 sortKey = sortKeyAlternative = phoneticName;
             } else if (name.fullNameStyle == FullNameStyle.CHINESE ||
                     name.fullNameStyle == FullNameStyle.CJK) {
-                sortKey = sortKeyAlternative = ContactLocaleUtils.getIntance()
-                        .getSortKey(displayName, name.fullNameStyle);
+                sortKey = sortKeyAlternative = displayName;
             }
 
             if (sortKey == null) {
@@ -2776,20 +2809,7 @@
                 organizationUpdate.bindLong(2, dataId);
                 organizationUpdate.execute();
 
-                String sortKey = null;
-                if (phoneticName == null && company != null) {
-                    int nameStyle = splitter.guessFullNameStyle(company);
-                    nameStyle = splitter.getAdjustedFullNameStyle(nameStyle);
-                    if (nameStyle == FullNameStyle.CHINESE ||
-                            nameStyle == FullNameStyle.CJK ) {
-                        sortKey = ContactLocaleUtils.getIntance()
-                                .getSortKey(company, nameStyle);
-                    }
-                }
-
-                if (sortKey == null) {
-                    sortKey = company;
-                }
+                String sortKey = company;
 
                 updateRawContact205(rawContactUpdate, rawContactId, company,
                         company, phoneticNameStyle, phoneticName, sortKey, sortKey);
@@ -3810,6 +3830,17 @@
         }
     }
 
+    private void upgradeToVersion707(SQLiteDatabase db) {
+        db.execSQL("ALTER TABLE " + Tables.RAW_CONTACTS
+                + " ADD " + RawContactsColumns.PHONEBOOK_LABEL_PRIMARY + " TEXT;");
+        db.execSQL("ALTER TABLE " + Tables.RAW_CONTACTS
+                + " ADD " + RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY + " INTEGER;");
+        db.execSQL("ALTER TABLE " + Tables.RAW_CONTACTS
+                + " ADD " + RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE + " TEXT;");
+        db.execSQL("ALTER TABLE " + Tables.RAW_CONTACTS
+                + " ADD " + RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE + " INTEGER;");
+    }
+
     public String extractHandleFromEmailAddress(String email) {
         Rfc822Token[] tokens = Rfc822Tokenizer.tokenize(email);
         if (tokens.length == 0) {
@@ -5172,9 +5203,7 @@
             }
             if (displayNameStyle == FullNameStyle.CHINESE ||
                     displayNameStyle == FullNameStyle.CJK) {
-                sortKeyPrimary = sortKeyAlternative =
-                        ContactLocaleUtils.getIntance().getSortKey(
-                                sortNamePrimary, displayNameStyle);
+                sortKeyPrimary = sortKeyAlternative = sortNamePrimary;
             }
         }
 
@@ -5183,6 +5212,21 @@
             sortKeyAlternative = sortNameAlternative;
         }
 
+        String phonebookLabelPrimary = "";
+        String phonebookLabelAlternative = "";
+        int phonebookBucketPrimary = 0;
+        int phonebookBucketAlternative = 0;
+        ContactLocaleUtils localeUtils = ContactLocaleUtils.getInstance();
+
+        if (sortKeyPrimary != null) {
+            phonebookBucketPrimary = localeUtils.getBucketIndex(sortKeyPrimary);
+            phonebookLabelPrimary = localeUtils.getBucketLabel(phonebookBucketPrimary);
+        }
+        if (sortKeyAlternative != null) {
+            phonebookBucketAlternative = localeUtils.getBucketIndex(sortKeyAlternative);
+            phonebookLabelAlternative = localeUtils.getBucketLabel(phonebookBucketAlternative);
+        }
+
         if (mRawContactDisplayNameUpdate == null) {
             mRawContactDisplayNameUpdate = db.compileStatement(
                     "UPDATE " + Tables.RAW_CONTACTS +
@@ -5193,7 +5237,11 @@
                             RawContacts.PHONETIC_NAME + "=?," +
                             RawContacts.PHONETIC_NAME_STYLE + "=?," +
                             RawContacts.SORT_KEY_PRIMARY + "=?," +
-                            RawContacts.SORT_KEY_ALTERNATIVE + "=?" +
+                            RawContactsColumns.PHONEBOOK_LABEL_PRIMARY + "=?," +
+                            RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY + "=?," +
+                            RawContacts.SORT_KEY_ALTERNATIVE + "=?," +
+                            RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE + "=?," +
+                            RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE + "=?" +
                     " WHERE " + RawContacts._ID + "=?");
         }
 
@@ -5203,8 +5251,12 @@
         bindString(mRawContactDisplayNameUpdate, 4, bestPhoneticName);
         mRawContactDisplayNameUpdate.bindLong(5, bestPhoneticNameStyle);
         bindString(mRawContactDisplayNameUpdate, 6, sortKeyPrimary);
-        bindString(mRawContactDisplayNameUpdate, 7, sortKeyAlternative);
-        mRawContactDisplayNameUpdate.bindLong(8, rawContactId);
+        bindString(mRawContactDisplayNameUpdate, 7, phonebookLabelPrimary);
+        mRawContactDisplayNameUpdate.bindLong(8, phonebookBucketPrimary);
+        bindString(mRawContactDisplayNameUpdate, 9, sortKeyAlternative);
+        bindString(mRawContactDisplayNameUpdate, 10, phonebookLabelAlternative);
+        mRawContactDisplayNameUpdate.bindLong(11, phonebookBucketAlternative);
+        mRawContactDisplayNameUpdate.bindLong(12, rawContactId);
         mRawContactDisplayNameUpdate.execute();
     }
 
diff --git a/src/com/android/providers/contacts/ContactsProvider2.java b/src/com/android/providers/contacts/ContactsProvider2.java
index d828458..1d88298 100644
--- a/src/com/android/providers/contacts/ContactsProvider2.java
+++ b/src/com/android/providers/contacts/ContactsProvider2.java
@@ -565,6 +565,10 @@
             .add(Contacts.SEND_TO_VOICEMAIL)
             .add(Contacts.SORT_KEY_ALTERNATIVE)
             .add(Contacts.SORT_KEY_PRIMARY)
+            .add(ContactsColumns.PHONEBOOK_LABEL_PRIMARY)
+            .add(ContactsColumns.PHONEBOOK_BUCKET_PRIMARY)
+            .add(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE)
+            .add(ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE)
             .add(Contacts.STARRED)
             .add(Contacts.TIMES_CONTACTED)
             .add(Contacts.HAS_PHONE_NUMBER)
@@ -752,6 +756,10 @@
             .add(RawContacts.PHONETIC_NAME_STYLE)
             .add(RawContacts.SORT_KEY_PRIMARY)
             .add(RawContacts.SORT_KEY_ALTERNATIVE)
+            .add(RawContactsColumns.PHONEBOOK_LABEL_PRIMARY)
+            .add(RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY)
+            .add(RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE)
+            .add(RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE)
             .add(RawContacts.TIMES_CONTACTED)
             .add(RawContacts.LAST_TIME_CONTACTED)
             .add(RawContacts.CUSTOM_RINGTONE)
@@ -1443,7 +1451,7 @@
         mNameLookupBuilder = new StructuredNameLookupBuilder(mNameSplitter);
         mPostalSplitter = new PostalSplitter(mCurrentLocale);
         mCommonNicknameCache = new CommonNicknameCache(mContactsHelper.getReadableDatabase());
-        ContactLocaleUtils.getIntance().setLocale(mCurrentLocale);
+        ContactLocaleUtils.setLocale(mCurrentLocale);
         mContactAggregator = new ContactAggregator(this, mContactsHelper,
                 createPhotoPriorityResolver(context), mNameSplitter, mCommonNicknameCache);
         mContactAggregator.setEnabled(SystemProperties.getBoolean(AGGREGATE_CONTACTS, true));
@@ -6011,8 +6019,10 @@
 
         qb.setStrict(true);
 
+        // Auto-rewrite SORT_KEY_{PRIMARY, ALTERNATIVE} sort orders.
+        String localizedSortOrder = getLocalizedSortOrder(sortOrder);
         Cursor cursor =
-                query(db, qb, projection, selection, selectionArgs, sortOrder, groupBy,
+                query(db, qb, projection, selection, selectionArgs, localizedSortOrder, groupBy,
                 having, limit, cancellationSignal);
 
         if (readBooleanQueryParameter(uri, ContactCounts.ADDRESS_BOOK_INDEX_EXTRAS, false)) {
@@ -6028,6 +6038,34 @@
     }
 
 
+    // Rewrites query sort orders using SORT_KEY_{PRIMARY, ALTERNATIVE}
+    // to use PHONEBOOK_BUCKET_{PRIMARY, ALTERNATIVE} as primary key; all
+    // other sort orders are returned unchanged. Preserves ordering
+    // (eg 'DESC') if present.
+    protected static String getLocalizedSortOrder(String sortOrder) {
+        String localizedSortOrder = sortOrder;
+        if (sortOrder != null) {
+            String sortKey;
+            String sortOrderSuffix = "";
+            int spaceIndex = sortOrder.indexOf(' ');
+            if (spaceIndex != -1) {
+                sortKey = sortOrder.substring(0, spaceIndex);
+                sortOrderSuffix = sortOrder.substring(spaceIndex);
+            } else {
+                sortKey = sortOrder;
+            }
+            if (TextUtils.equals(sortKey, Contacts.SORT_KEY_PRIMARY)) {
+                localizedSortOrder = ContactsColumns.PHONEBOOK_BUCKET_PRIMARY
+                    + sortOrderSuffix + ", " + sortOrder;
+            } else if (TextUtils.equals(sortKey, Contacts.SORT_KEY_ALTERNATIVE)) {
+                localizedSortOrder = ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE
+                    + sortOrderSuffix + ", " + sortOrder;
+            }
+        }
+        return localizedSortOrder;
+    }
+
+
     private Cursor query(final SQLiteDatabase db, SQLiteQueryBuilder qb, String[] projection,
             String selection, String[] selectionArgs, String sortOrder, String groupBy,
             String having, String limit, CancellationSignal cancellationSignal) {
@@ -6122,7 +6160,7 @@
                 final long start = System.currentTimeMillis();
 
                 b = getFastScrollingIndexExtras(queryUri, db, qb, selection, selectionArgs,
-                        sortOrder, countExpression, cancellationSignal, getLocale());
+                        sortOrder, countExpression, cancellationSignal);
 
                 final long end = System.currentTimeMillis();
                 final int time = (int) (end - start);
@@ -6139,19 +6177,22 @@
 
     private static final class AddressBookIndexQuery {
         public static final String NAME = "name";
+        public static final String BUCKET = "bucket";
         public static final String LABEL = "label";
         public static final String COUNT = "count";
 
         public static final String[] COLUMNS = new String[] {
-                NAME, LABEL, COUNT
+            NAME, BUCKET, LABEL, COUNT
         };
 
         public static final int COLUMN_NAME = 0;
-        public static final int COLUMN_LABEL = 1;
-        public static final int COLUMN_COUNT = 2;
+        public static final int COLUMN_BUCKET = 1;
+        public static final int COLUMN_LABEL = 2;
+        public static final int COLUMN_COUNT = 3;
 
-        // PHONEBOOK collator registered in sqlite3_android.cpp
-        public static final String ORDER_BY = NAME + " COLLATE " + PHONEBOOK_COLLATOR_NAME;
+        public static final String GROUP_BY = BUCKET + ", " + LABEL;
+        public static final String ORDER_BY =
+            BUCKET + ", " +  NAME + " COLLATE " + PHONEBOOK_COLLATOR_NAME;
     }
 
     /**
@@ -6161,7 +6202,7 @@
     private static Bundle getFastScrollingIndexExtras(final Uri queryUri, final SQLiteDatabase db,
             final SQLiteQueryBuilder qb, final String selection, final String[] selectionArgs,
             final String sortOrder, String countExpression,
-            final CancellationSignal cancellationSignal, final Locale currentLocale) {
+            final CancellationSignal cancellationSignal) {
         String sortKey;
 
         // The sort order suffix could be something like "DESC".
@@ -6180,69 +6221,53 @@
             sortKey = Contacts.SORT_KEY_PRIMARY;
         }
 
+        String bucketKey;
+        String labelKey;
+        if (TextUtils.equals(sortKey, Contacts.SORT_KEY_PRIMARY)) {
+            bucketKey = ContactsColumns.PHONEBOOK_BUCKET_PRIMARY;
+            labelKey = ContactsColumns.PHONEBOOK_LABEL_PRIMARY;
+        } else if (TextUtils.equals(sortKey, Contacts.SORT_KEY_ALTERNATIVE)) {
+            bucketKey = ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE;
+            labelKey = ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE;
+        } else {
+            return null;
+        }
+
         HashMap<String, String> projectionMap = Maps.newHashMap();
         projectionMap.put(AddressBookIndexQuery.NAME,
                 sortKey + " AS " + AddressBookIndexQuery.NAME);
+        projectionMap.put(AddressBookIndexQuery.BUCKET,
+                bucketKey + " AS " + AddressBookIndexQuery.BUCKET);
+        projectionMap.put(AddressBookIndexQuery.LABEL,
+                labelKey + " AS " + AddressBookIndexQuery.LABEL);
 
         // If "what to count" is not specified, we just count all records.
         if (TextUtils.isEmpty(countExpression)) {
             countExpression = "*";
         }
 
-        /**
-         * Use the GET_PHONEBOOK_INDEX function, which is an android extension for SQLite3,
-         * to map the sort key to a character that is traditionally used in phonebooks to
-         * label its section.  For example, in Korean it will be the first consonant in the
-         * letter; for Japanese it will be Hiragana rather than Katakana. Note the label may
-         * be more than one character in some languages, such as "CH" in Czech.
-         */
-        projectionMap.put(AddressBookIndexQuery.LABEL,
-                "GET_PHONEBOOK_INDEX(" + sortKey + ",'" + currentLocale.toString() + "')"
-                        + " AS " + AddressBookIndexQuery.LABEL);
         projectionMap.put(AddressBookIndexQuery.COUNT,
                 "COUNT(" + countExpression + ") AS " + AddressBookIndexQuery.COUNT);
         qb.setProjectionMap(projectionMap);
+        String orderBy = AddressBookIndexQuery.BUCKET + sortOrderSuffix
+            + ", " + AddressBookIndexQuery.NAME + " COLLATE "
+            + PHONEBOOK_COLLATOR_NAME + sortOrderSuffix;
 
         Cursor indexCursor = qb.query(db, AddressBookIndexQuery.COLUMNS, selection, selectionArgs,
-                AddressBookIndexQuery.ORDER_BY, null /* having */,
-                AddressBookIndexQuery.ORDER_BY + sortOrderSuffix,
-                null, cancellationSignal);
+                AddressBookIndexQuery.GROUP_BY, null /* having */,
+                orderBy, null, cancellationSignal);
 
         try {
-            int groupCount = indexCursor.getCount();
-            String labels[] = new String[groupCount];
-            int counts[] = new int[groupCount];
-            int indexCount = 0;
-            String currentLabel = null;
+            int numLabels = indexCursor.getCount();
+            String labels[] = new String[numLabels];
+            int counts[] = new int[numLabels];
 
-            // Since GET_PHONEBOOK_INDEX is a many-to-1 function, we may end up
-            // with multiple entries for the same label.  The following code
-            // collapses those duplicates.
-            for (int i = 0; i < groupCount; i++) {
+            for (int i = 0; i < numLabels; i++) {
                 indexCursor.moveToNext();
-                String label = indexCursor.getString(AddressBookIndexQuery.COLUMN_LABEL);
-                if (label == null) {
-                    label = "";
-                }
-                int count = indexCursor.getInt(AddressBookIndexQuery.COLUMN_COUNT);
-                if (indexCount == 0 || !TextUtils.equals(label, currentLabel)) {
-                    labels[indexCount] = currentLabel = label;
-                    counts[indexCount] = count;
-                    indexCount++;
-                } else {
-                    counts[indexCount - 1] += count;
-                }
+                labels[i] = indexCursor.getString(AddressBookIndexQuery.COLUMN_LABEL);
+                counts[i] = indexCursor.getInt(AddressBookIndexQuery.COLUMN_COUNT);
             }
 
-            if (indexCount < groupCount) {
-                String[] newLabels = new String[indexCount];
-                System.arraycopy(labels, 0, newLabels, 0, indexCount);
-                labels = newLabels;
-
-                int[] newCounts = new int[indexCount];
-                System.arraycopy(counts, 0, newCounts, 0, indexCount);
-                counts = newCounts;
-            }
             return FastScrollingIndexCache.buildExtraBundle(labels, counts);
         } finally {
             indexCursor.close();
diff --git a/src/com/android/providers/contacts/NameLookupBuilder.java b/src/com/android/providers/contacts/NameLookupBuilder.java
index 8375b88..67dae46 100644
--- a/src/com/android/providers/contacts/NameLookupBuilder.java
+++ b/src/com/android/providers/contacts/NameLookupBuilder.java
@@ -321,7 +321,7 @@
 
     private void appendNameShorthandLookup(IndexBuilder builder, String name, int fullNameStyle) {
         Iterator<String> it =
-                ContactLocaleUtils.getIntance().getNameLookupKeys(name, fullNameStyle);
+                ContactLocaleUtils.getInstance().getNameLookupKeys(name, fullNameStyle);
         if (it != null) {
             while (it.hasNext()) {
                 builder.appendName(it.next());
diff --git a/tests/src/com/android/providers/contacts/ContactLocaleUtilsTest.java b/tests/src/com/android/providers/contacts/ContactLocaleUtilsTest.java
index cf18155..b43cff2 100644
--- a/tests/src/com/android/providers/contacts/ContactLocaleUtilsTest.java
+++ b/tests/src/com/android/providers/contacts/ContactLocaleUtilsTest.java
@@ -21,6 +21,7 @@
 import android.test.suitebuilder.annotation.SmallTest;
 
 import java.text.Collator;
+import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.Iterator;
@@ -28,7 +29,11 @@
 
 @SmallTest
 public class ContactLocaleUtilsTest extends AndroidTestCase {
+    private static final String PHONE_NUMBER_1 = "+1 (650) 555-1212";
+    private static final String PHONE_NUMBER_2 = "650-555-1212";
     private static final String LATIN_NAME = "John Smith";
+    private static final String LATIN_NAME_2 = "John Paul Jones";
+    private static final String KANJI_NAME = "\u65e5";
     private static final String CHINESE_NAME = "\u675C\u9D51";
     private static final String CHINESE_LATIN_MIX_NAME_1 = "D\u675C\u9D51";
     private static final String CHINESE_LATIN_MIX_NAME_2 = "MARY \u675C\u9D51";
@@ -39,15 +44,87 @@
     private static final String[] CHINESE_LATIN_MIX_NAME_2_KEY = {"\u9D51", "\u675C\u9D51",
         "MARY \u675C\u9D51", "JUAN", "DUJUAN", "MARY DUJUAN", "J", "DJ", "MDJ"};
     private static final String[] LATIN_NAME_KEY = {"John Smith", "Smith", "JS", "S"};
+    private static final String[] LATIN_NAME_KEY_2 = {
+        "John Paul Jones", "Paul Jones", "Jones", "JPJ", "PJ", "J"};
+    private static final String[] LABELS_EN_US = {
+        "", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",
+        "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z",
+        "#", ""};
+    private static final String[] LABELS_JA_JP = {
+        "", "\u3042", "\u304B", "\u3055", "\u305F", "\u306A", "\u306F",
+        "\u307E", "\u3084", "\u3089", "\u308F", "\u4ED6",
+        "", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",
+        "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z",
+        "#", ""};
+    private static final String[] LABELS_ZH_TW = {
+        "", "1\u5283", "2\u5283", "3\u5283", "4\u5283", "5\u5283", "6\u5283",
+        "7\u5283", "8\u5283", "9\u5283", "10\u5283", "11\u5283", "12\u5283",
+        "13\u5283", "14\u5283", "15\u5283", "16\u5283", "17\u5283", "18\u5283",
+        "19\u5283", "20\u5283", "21\u5283", "22\u5283", "23\u5283", "24\u5283",
+        "25\u5283",
+        "", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",
+        "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z",
+        "#", ""};
+    private static final String[] LABELS_KO = {
+        "",  "\u1100", "\u1102", "\u1103", "\u1105", "\u1106", "\u1107",
+        "\u1109", "\u110B", "\u110C", "\u110E", "\u110F", "\u1110", "\u1111",
+        "\u1112",
+        "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M",
+        "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z",
+        "#", ""};
 
+    private static final String JAPANESE_MISC = "\u4ed6";
 
-    private ContactLocaleUtils mContactLocaleUtils = ContactLocaleUtils.getIntance();
+    private String getLabel(String name) {
+        ContactLocaleUtils utils = ContactLocaleUtils.getInstance();
+        int bucketIndex = utils.getBucketIndex(name);
+        return utils.getBucketLabel(bucketIndex);
+    }
 
-    public void testContactLocaleUtilsBase() throws Exception {
-        assertEquals(mContactLocaleUtils.getSortKey(LATIN_NAME, FullNameStyle.UNDEFINED),
-                LATIN_NAME);
-        assertNull(mContactLocaleUtils.getNameLookupKeys(LATIN_NAME,
-                FullNameStyle.UNDEFINED));
+    private Iterator<String> getNameLookupKeys(String name, int nameStyle) {
+        ContactLocaleUtils utils = ContactLocaleUtils.getInstance();
+        return utils.getNameLookupKeys(name, nameStyle);
+    }
+
+    private ArrayList<String> getLabels() {
+        ContactLocaleUtils utils = ContactLocaleUtils.getInstance();
+        return utils.getLabels();
+    }
+
+    public void testEnglishContactLocaleUtils() throws Exception {
+        ContactLocaleUtils.setLocale(Locale.ENGLISH);
+        assertEquals("#", getLabel(PHONE_NUMBER_1));
+        assertEquals("#", getLabel(PHONE_NUMBER_2));
+        assertEquals("J", getLabel(LATIN_NAME));
+        assertEquals("", getLabel(CHINESE_NAME));
+        assertEquals("D", getLabel(CHINESE_LATIN_MIX_NAME_1));
+        assertEquals("B", getLabel("Bob Smith"));
+
+        assertNull(getNameLookupKeys(LATIN_NAME, FullNameStyle.UNDEFINED));
+        verifyLabels(getLabels(), LABELS_EN_US);
+    }
+
+    public void testJapaneseContactLocaleUtils() throws Exception {
+        if (!hasJapaneseCollator()) {
+            return;
+        }
+
+        ContactLocaleUtils.setLocale(Locale.JAPAN);
+        assertEquals("#", getLabel(PHONE_NUMBER_1));
+        assertEquals("#", getLabel(PHONE_NUMBER_2));
+        assertEquals(JAPANESE_MISC, getLabel(KANJI_NAME));
+        assertEquals("J", getLabel(LATIN_NAME));
+        assertEquals(JAPANESE_MISC, getLabel(CHINESE_NAME));
+        assertEquals("D", getLabel(CHINESE_LATIN_MIX_NAME_1));
+
+        assertNull(getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK));
+        Iterator<String> keys = getNameLookupKeys(CHINESE_NAME,
+                FullNameStyle.CHINESE);
+        verifyKeys(keys, CHINESE_NAME_KEY);
+
+        // Following two tests are broken with ICU 4.9
+        verifyLabels(getLabels(), LABELS_JA_JP);
+        assertEquals("B", getLabel("Bob Smith"));
     }
 
     public void testChineseContactLocaleUtils() throws Exception {
@@ -55,56 +132,68 @@
             return;
         }
 
-        assertTrue(mContactLocaleUtils.getSortKey(CHINESE_NAME,
-                FullNameStyle.CHINESE).equalsIgnoreCase("DU \u675C JUAN \u9D51"));
+        ContactLocaleUtils.setLocale(Locale.SIMPLIFIED_CHINESE);
+        assertEquals("#", getLabel(PHONE_NUMBER_1));
+        assertEquals("#", getLabel(PHONE_NUMBER_2));
+        assertEquals("J", getLabel(LATIN_NAME));
+        assertEquals("D", getLabel(CHINESE_NAME));
+        assertEquals("D", getLabel(CHINESE_LATIN_MIX_NAME_1));
+        assertEquals("B", getLabel("Bob Smith"));
+        verifyLabels(getLabels(), LABELS_EN_US);
 
-        assertTrue(mContactLocaleUtils.getSortKey(CHINESE_LATIN_MIX_NAME_1,
-                FullNameStyle.CHINESE).equalsIgnoreCase("d DU \u675C JUAN \u9D51"));
+        ContactLocaleUtils.setLocale(Locale.TRADITIONAL_CHINESE);
+        assertEquals("#", getLabel(PHONE_NUMBER_1));
+        assertEquals("#", getLabel(PHONE_NUMBER_2));
+        assertEquals("J", getLabel(LATIN_NAME));
+        assertEquals("12\u5283", getLabel(CHINESE_NAME));
+        assertEquals("D", getLabel(CHINESE_LATIN_MIX_NAME_1));
 
-        assertTrue(mContactLocaleUtils.getSortKey(CHINESE_LATIN_MIX_NAME_2,
-                FullNameStyle.CHINESE).equalsIgnoreCase("mary DU \u675C JUAN \u9D51"));
-
-        Iterator<String> keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_NAME,
+        ContactLocaleUtils.setLocale(Locale.SIMPLIFIED_CHINESE);
+        Iterator<String> keys = getNameLookupKeys(CHINESE_NAME,
                 FullNameStyle.CHINESE);
         verifyKeys(keys, CHINESE_NAME_KEY);
 
-        keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_LATIN_MIX_NAME_1,
-                FullNameStyle.CHINESE);
+        keys = getNameLookupKeys(CHINESE_LATIN_MIX_NAME_1, FullNameStyle.CHINESE);
         verifyKeys(keys, CHINESE_LATIN_MIX_NAME_1_KEY);
 
-        keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_LATIN_MIX_NAME_2,
-                FullNameStyle.CHINESE);
+        keys = getNameLookupKeys(CHINESE_LATIN_MIX_NAME_2, FullNameStyle.CHINESE);
         verifyKeys(keys, CHINESE_LATIN_MIX_NAME_2_KEY);
+
+        // Following test broken with ICU 4.9
+        ContactLocaleUtils.setLocale(Locale.TRADITIONAL_CHINESE);
+        verifyLabels(getLabels(), LABELS_ZH_TW);
+        assertEquals("B", getLabel("Bob Smith"));
     }
 
     public void testChineseStyleNameWithDifferentLocale() throws Exception {
         if (!hasChineseCollator()) {
             return;
         }
-        mContactLocaleUtils.setLocale(Locale.ENGLISH);
-        assertEquals("DU \u675C JUAN \u9D51",
-                mContactLocaleUtils.getSortKey(CHINESE_NAME, FullNameStyle.CHINESE).toUpperCase());
-        assertEquals("DU \u675C JUAN \u9D51",
-                mContactLocaleUtils.getSortKey(CHINESE_NAME, FullNameStyle.CJK).toUpperCase());
-        mContactLocaleUtils.setLocale(Locale.CHINESE);
-        assertEquals("DU \u675C JUAN \u9D51",
-                mContactLocaleUtils.getSortKey(CHINESE_NAME, FullNameStyle.CHINESE).toUpperCase());
-        assertEquals("DU \u675C JUAN \u9D51",
-                mContactLocaleUtils.getSortKey(CHINESE_NAME, FullNameStyle.CJK).toUpperCase());
-        assertEquals(LATIN_NAME, mContactLocaleUtils.getSortKey(LATIN_NAME, FullNameStyle.WESTERN));
 
-        mContactLocaleUtils.setLocale(Locale.ENGLISH);
-        Iterator<String> keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_NAME,
+        ContactLocaleUtils.setLocale(Locale.ENGLISH);
+        Iterator<String> keys = getNameLookupKeys(CHINESE_NAME,
                 FullNameStyle.CHINESE);
         verifyKeys(keys, CHINESE_NAME_KEY);
-        keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK);
+        keys = getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK);
         verifyKeys(keys, CHINESE_NAME_KEY);
-        mContactLocaleUtils.setLocale(Locale.CHINESE);
-        keys = mContactLocaleUtils.getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK);
-        verifyKeys(keys, CHINESE_NAME_KEY);
-        keys = mContactLocaleUtils.getNameLookupKeys(LATIN_NAME, FullNameStyle.WESTERN);
-        verifyKeys(keys, LATIN_NAME_KEY);
 
+        ContactLocaleUtils.setLocale(Locale.CHINESE);
+        keys = getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK);
+        verifyKeys(keys, CHINESE_NAME_KEY);
+        keys = getNameLookupKeys(LATIN_NAME, FullNameStyle.WESTERN);
+        verifyKeys(keys, LATIN_NAME_KEY);
+        keys = getNameLookupKeys(LATIN_NAME_2, FullNameStyle.WESTERN);
+        verifyKeys(keys, LATIN_NAME_KEY_2);
+
+        ContactLocaleUtils.setLocale(Locale.TRADITIONAL_CHINESE);
+        keys = getNameLookupKeys(CHINESE_NAME, FullNameStyle.CJK);
+        verifyKeys(keys, CHINESE_NAME_KEY);
+    }
+
+    public void testKoreanContactLocaleUtils() throws Exception {
+        ContactLocaleUtils.setLocale(Locale.KOREA);
+        assertEquals("B", getLabel("Bob Smith"));
+        verifyLabels(getLabels(), LABELS_KO);
     }
 
     private void verifyKeys(final Iterator<String> resultKeys, final String[] expectedKeys)
@@ -113,7 +202,14 @@
         while (resultKeys.hasNext()) {
             allKeys.add(resultKeys.next());
         }
-        assertEquals(allKeys, new HashSet<String>(Arrays.asList(expectedKeys)));
+        assertEquals(new HashSet<String>(Arrays.asList(expectedKeys)), allKeys);
+    }
+
+    private void verifyLabels(final ArrayList<String> resultLabels,
+                              final String[] expectedLabels)
+            throws Exception {
+        assertEquals(new ArrayList<String>(Arrays.asList(expectedLabels)),
+                     resultLabels);
     }
 
     private boolean hasChineseCollator() {
@@ -125,4 +221,14 @@
         }
         return false;
     }
+
+    private boolean hasJapaneseCollator() {
+        final Locale locale[] = Collator.getAvailableLocales();
+        for (int i = 0; i < locale.length; i++) {
+            if (locale[i].equals(Locale.JAPAN)) {
+                return true;
+            }
+        }
+        return false;
+    }
 }
diff --git a/tests/src/com/android/providers/contacts/ContactsProvider2Test.java b/tests/src/com/android/providers/contacts/ContactsProvider2Test.java
index 1011ae2..9bcf54c 100644
--- a/tests/src/com/android/providers/contacts/ContactsProvider2Test.java
+++ b/tests/src/com/android/providers/contacts/ContactsProvider2Test.java
@@ -69,9 +69,11 @@
 import com.android.internal.util.ArrayUtils;
 import com.android.providers.contacts.ContactsDatabaseHelper;
 import com.android.providers.contacts.ContactsDatabaseHelper.AggregationExceptionColumns;
+import com.android.providers.contacts.ContactsDatabaseHelper.ContactsColumns;
 import com.android.providers.contacts.ContactsDatabaseHelper.DataUsageStatColumns;
 import com.android.providers.contacts.ContactsDatabaseHelper.DbProperties;
 import com.android.providers.contacts.ContactsDatabaseHelper.PresenceColumns;
+import com.android.providers.contacts.ContactsDatabaseHelper.RawContactsColumns;
 import com.android.providers.contacts.ContactsDatabaseHelper.Tables;
 import com.android.providers.contacts.tests.R;
 import com.google.android.collect.Lists;
@@ -112,6 +114,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -146,6 +152,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -184,6 +194,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -224,6 +238,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -271,6 +289,10 @@
                 RawContacts.NAME_VERIFIED,
                 RawContacts.SORT_KEY_PRIMARY,
                 RawContacts.SORT_KEY_ALTERNATIVE,
+                RawContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                RawContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                RawContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 RawContacts.TIMES_CONTACTED,
                 RawContacts.LAST_TIME_CONTACTED,
                 RawContacts.CUSTOM_RINGTONE,
@@ -337,6 +359,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -406,6 +432,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -490,6 +520,10 @@
                 Contacts.PHONETIC_NAME_STYLE,
                 Contacts.SORT_KEY_PRIMARY,
                 Contacts.SORT_KEY_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_LABEL_PRIMARY,
+                ContactsColumns.PHONEBOOK_BUCKET_PRIMARY,
+                ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE,
+                ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE,
                 Contacts.LAST_TIME_CONTACTED,
                 Contacts.TIMES_CONTACTED,
                 Contacts.STARRED,
@@ -1212,7 +1246,6 @@
         // Sanity test. Run tests for "Chilled Guacamole" again and see nothing changes
         // after the Sip address being inserted.
         assertStoredValues(filterUri2, values);
-        assertStoredValues(filterUri3, values);
         assertEquals(0, getCount(filterUri4, null, null));
         assertEquals(0, getCount(filterUri5, null, null));
         assertStoredValues(filterUri6, new ContentValues[] {values1, values2, values3} );
@@ -3034,6 +3067,7 @@
     }
 
     public void testContactWithoutPhoneticName() {
+        ContactLocaleUtils.setLocale(Locale.ENGLISH);
         final long rawContactId = createRawContact(null);
 
         ContentValues values = new ContentValues();
@@ -3051,7 +3085,9 @@
         values.putNull(RawContacts.PHONETIC_NAME);
         values.put(RawContacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
         values.put(RawContacts.SORT_KEY_PRIMARY, "John K. Doe, Jr.");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_PRIMARY, "J");
         values.put(RawContacts.SORT_KEY_ALTERNATIVE, "Doe, John K., Jr.");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "D");
 
         Uri rawContactUri = ContentUris.withAppendedId(RawContacts.CONTENT_URI, rawContactId);
         assertStoredValues(rawContactUri, values);
@@ -3063,7 +3099,9 @@
         values.putNull(Contacts.PHONETIC_NAME);
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
         values.put(Contacts.SORT_KEY_PRIMARY, "John K. Doe, Jr.");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "J");
         values.put(Contacts.SORT_KEY_ALTERNATIVE, "Doe, John K., Jr.");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "D");
 
         Uri contactUri = ContentUris.withAppendedId(Contacts.CONTENT_URI,
                 queryContactId(rawContactId));
@@ -3074,15 +3112,15 @@
     }
 
     public void testContactWithChineseName() {
-
-        // Only run this test when Chinese collation is supported
-        if (!Arrays.asList(Collator.getAvailableLocales()).contains(Locale.CHINA)) {
+        if (!hasChineseCollator()) {
             return;
         }
+        ContactLocaleUtils.setLocale(Locale.SIMPLIFIED_CHINESE);
 
         long rawContactId = createRawContact(null);
 
         ContentValues values = new ContentValues();
+        // "DUAN \u6BB5 XIAO \u5C0F TAO \u6D9B"
         values.put(StructuredName.DISPLAY_NAME, "\u6BB5\u5C0F\u6D9B");
         Uri dataUri = insertStructuredName(rawContactId, values);
 
@@ -3092,8 +3130,10 @@
         values.put(RawContacts.DISPLAY_NAME_ALTERNATIVE, "\u6BB5\u5C0F\u6D9B");
         values.putNull(RawContacts.PHONETIC_NAME);
         values.put(RawContacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
-        values.put(RawContacts.SORT_KEY_PRIMARY, "DUAN \u6BB5 XIAO \u5C0F TAO \u6D9B");
-        values.put(RawContacts.SORT_KEY_ALTERNATIVE, "DUAN \u6BB5 XIAO \u5C0F TAO \u6D9B");
+        values.put(RawContacts.SORT_KEY_PRIMARY, "\u6BB5\u5C0F\u6D9B");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_PRIMARY, "D");
+        values.put(RawContacts.SORT_KEY_ALTERNATIVE, "\u6BB5\u5C0F\u6D9B");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "D");
 
         Uri rawContactUri = ContentUris.withAppendedId(RawContacts.CONTENT_URI, rawContactId);
         assertStoredValues(rawContactUri, values);
@@ -3104,8 +3144,10 @@
         values.put(Contacts.DISPLAY_NAME_ALTERNATIVE, "\u6BB5\u5C0F\u6D9B");
         values.putNull(Contacts.PHONETIC_NAME);
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
-        values.put(Contacts.SORT_KEY_PRIMARY, "DUAN \u6BB5 XIAO \u5C0F TAO \u6D9B");
-        values.put(Contacts.SORT_KEY_ALTERNATIVE, "DUAN \u6BB5 XIAO \u5C0F TAO \u6D9B");
+        values.put(Contacts.SORT_KEY_PRIMARY, "\u6BB5\u5C0F\u6D9B");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "D");
+        values.put(Contacts.SORT_KEY_ALTERNATIVE, "\u6BB5\u5C0F\u6D9B");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "D");
 
         Uri contactUri = ContentUris.withAppendedId(Contacts.CONTENT_URI,
                 queryContactId(rawContactId));
@@ -3116,6 +3158,10 @@
     }
 
     public void testContactWithJapaneseName() {
+        if (!hasJapaneseCollator()) {
+            return;
+        }
+        ContactLocaleUtils.setLocale(Locale.JAPAN);
         long rawContactId = createRawContact(null);
 
         ContentValues values = new ContentValues();
@@ -3131,6 +3177,8 @@
         values.put(RawContacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.JAPANESE);
         values.put(RawContacts.SORT_KEY_PRIMARY, "\u304B\u3044\u304F\u3046");
         values.put(RawContacts.SORT_KEY_ALTERNATIVE, "\u304B\u3044\u304F\u3046");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_PRIMARY, "\u304B");
+        values.put(RawContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "\u304B");
 
         Uri rawContactUri = ContentUris.withAppendedId(RawContacts.CONTENT_URI, rawContactId);
         assertStoredValues(rawContactUri, values);
@@ -3143,6 +3191,8 @@
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.JAPANESE);
         values.put(Contacts.SORT_KEY_PRIMARY, "\u304B\u3044\u304F\u3046");
         values.put(Contacts.SORT_KEY_ALTERNATIVE, "\u304B\u3044\u304F\u3046");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "\u304B");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "\u304B");
 
         Uri contactUri = ContentUris.withAppendedId(Contacts.CONTENT_URI,
                 queryContactId(rawContactId));
@@ -3230,10 +3280,16 @@
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
         values.put(Contacts.SORT_KEY_PRIMARY, "Monsters Inc");
         values.put(Contacts.SORT_KEY_ALTERNATIVE, "Monsters Inc");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "M");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "M");
         assertStoredValues(uri, values);
     }
 
     public void testDisplayNameFromOrganizationWithJapanesePhoneticName() {
+        if (!hasJapaneseCollator()) {
+            return;
+        }
+        ContactLocaleUtils.setLocale(Locale.JAPAN);
         long rawContactId = createRawContact();
         long contactId = queryContactId(rawContactId);
         ContentValues values = new ContentValues();
@@ -3252,22 +3308,16 @@
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.JAPANESE);
         values.put(Contacts.SORT_KEY_PRIMARY, "\u30C9\u30B3\u30E2");
         values.put(Contacts.SORT_KEY_ALTERNATIVE, "\u30C9\u30B3\u30E2");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "\u305F");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "\u305F");
         assertStoredValues(uri, values);
     }
 
     public void testDisplayNameFromOrganizationWithChineseName() {
-        boolean hasChineseCollator = false;
-        final Locale locale[] = Collator.getAvailableLocales();
-        for (int i = 0; i < locale.length; i++) {
-            if (locale[i].equals(Locale.CHINA)) {
-                hasChineseCollator = true;
-                break;
-            }
-        }
-
-        if (!hasChineseCollator) {
+        if (!hasChineseCollator()) {
             return;
         }
+        ContactLocaleUtils.setLocale(Locale.SIMPLIFIED_CHINESE);
 
         long rawContactId = createRawContact();
         long contactId = queryContactId(rawContactId);
@@ -3284,8 +3334,10 @@
         values.put(Contacts.DISPLAY_NAME, "\u4E2D\u56FD\u7535\u4FE1");
         values.putNull(Contacts.PHONETIC_NAME);
         values.put(Contacts.PHONETIC_NAME_STYLE, PhoneticNameStyle.UNDEFINED);
-        values.put(Contacts.SORT_KEY_PRIMARY, "ZHONG \u4E2D GUO \u56FD DIAN \u7535 XIN \u4FE1");
-        values.put(Contacts.SORT_KEY_ALTERNATIVE, "ZHONG \u4E2D GUO \u56FD DIAN \u7535 XIN \u4FE1");
+        values.put(Contacts.SORT_KEY_PRIMARY, "\u4E2D\u56FD\u7535\u4FE1");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_PRIMARY, "Z");
+        values.put(Contacts.SORT_KEY_ALTERNATIVE, "\u4E2D\u56FD\u7535\u4FE1");
+        values.put(ContactsColumns.PHONEBOOK_LABEL_ALTERNATIVE, "Z");
         assertStoredValues(uri, values);
     }
 
@@ -6186,6 +6238,23 @@
         testChangingPrimary(true, true);
     }
 
+    public void testContactSortOrder() {
+        assertEquals(ContactsColumns.PHONEBOOK_BUCKET_PRIMARY + ", "
+                     + Contacts.SORT_KEY_PRIMARY,
+                     ContactsProvider2.getLocalizedSortOrder(Contacts.SORT_KEY_PRIMARY));
+        assertEquals(ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE + ", "
+                     + Contacts.SORT_KEY_ALTERNATIVE,
+                     ContactsProvider2.getLocalizedSortOrder(Contacts.SORT_KEY_ALTERNATIVE));
+        assertEquals(ContactsColumns.PHONEBOOK_BUCKET_PRIMARY + " DESC, "
+                     + Contacts.SORT_KEY_PRIMARY + " DESC",
+                     ContactsProvider2.getLocalizedSortOrder(Contacts.SORT_KEY_PRIMARY + " DESC"));
+        String suffix = " COLLATE LOCALIZED DESC";
+        assertEquals(ContactsColumns.PHONEBOOK_BUCKET_ALTERNATIVE + suffix
+                     + ", " + Contacts.SORT_KEY_ALTERNATIVE + suffix,
+                     ContactsProvider2.getLocalizedSortOrder(Contacts.SORT_KEY_ALTERNATIVE
+                                                             + suffix));
+    }
+
     public void testContactCounts() {
         Uri uri = Contacts.CONTENT_URI.buildUpon()
                 .appendQueryParameter(ContactCounts.ADDRESS_BOOK_INDEX_EXTRAS, "true").build();
@@ -6201,7 +6270,7 @@
 
         Cursor cursor = mResolver.query(uri,
                 new String[]{Contacts.DISPLAY_NAME},
-                null, null, Contacts.SORT_KEY_PRIMARY + " COLLATE LOCALIZED");
+                null, null, Contacts.SORT_KEY_PRIMARY);
 
         assertFirstLetterValues(cursor, "", "B", "J", "M", "R", "T");
         assertFirstLetterCounts(cursor,    1,   1,   1,   2,   2,   1);
@@ -7266,4 +7335,24 @@
                 .appendQueryParameter(DataUsageFeedback.USAGE_TYPE, usageType)
                 .build(), new ContentValues(), null, null);
     }
+
+    private boolean hasChineseCollator() {
+        final Locale locale[] = Collator.getAvailableLocales();
+        for (int i = 0; i < locale.length; i++) {
+            if (locale[i].equals(Locale.CHINA)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private boolean hasJapaneseCollator() {
+        final Locale locale[] = Collator.getAvailableLocales();
+        for (int i = 0; i < locale.length; i++) {
+            if (locale[i].equals(Locale.JAPAN)) {
+                return true;
+            }
+        }
+        return false;
+    }
 }