diff --git a/java/src/com/android/inputmethod/accessibility/AccessibilityEntityProvider.java b/java/src/com/android/inputmethod/accessibility/AccessibilityEntityProvider.java
index c628c5b..063f211 100644
--- a/java/src/com/android/inputmethod/accessibility/AccessibilityEntityProvider.java
+++ b/java/src/com/android/inputmethod/accessibility/AccessibilityEntityProvider.java
@@ -159,8 +159,7 @@
 
             // Add the virtual children of the root View.
             final Keyboard keyboard = mKeyboardView.getKeyboard();
-            final Key[] keys = keyboard.getKeys();
-            for (Key key : keys) {
+            for (final Key key : keyboard.getSortedKeys()) {
                 final int childVirtualViewId = generateVirtualViewIdForKey(key);
                 rootInfo.addChild(mKeyboardView, childVirtualViewId);
             }
@@ -308,8 +307,7 @@
         }
         mVirtualViewIdToKey.clear();
 
-        final Key[] keys = keyboard.getKeys();
-        for (Key key : keys) {
+        for (final Key key : keyboard.getSortedKeys()) {
             final int virtualViewId = generateVirtualViewIdForKey(key);
             mVirtualViewIdToKey.put(virtualViewId, key);
         }
diff --git a/java/src/com/android/inputmethod/keyboard/EmojiPalettesView.java b/java/src/com/android/inputmethod/keyboard/EmojiPalettesView.java
index ad99697..d8b5758 100644
--- a/java/src/com/android/inputmethod/keyboard/EmojiPalettesView.java
+++ b/java/src/com/android/inputmethod/keyboard/EmojiPalettesView.java
@@ -58,9 +58,10 @@
 import com.android.inputmethod.latin.utils.ResourceUtils;
 
 import java.util.ArrayList;
-import java.util.Arrays;
+import java.util.Collections;
 import java.util.Comparator;
 import java.util.HashMap;
+import java.util.List;
 import java.util.concurrent.ConcurrentHashMap;
 import java.util.concurrent.TimeUnit;
 
@@ -297,7 +298,7 @@
 
         private int getCategoryPageCount(final int categoryId) {
             final Keyboard keyboard = mLayoutSet.getKeyboard(sCategoryElementId[categoryId]);
-            return (keyboard.getKeys().length - 1) / mMaxPageKeyCount + 1;
+            return (keyboard.getSortedKeys().size() - 1) / mMaxPageKeyCount + 1;
         }
 
         // Returns a pair of the category id and the category page id from the view pager's page
@@ -346,7 +347,8 @@
                 }
 
                 final Keyboard keyboard = mLayoutSet.getKeyboard(sCategoryElementId[categoryId]);
-                final Key[][] sortedKeys = sortKeysIntoPages(keyboard.getKeys(), mMaxPageKeyCount);
+                final Key[][] sortedKeys = sortKeysIntoPages(
+                        keyboard.getSortedKeys(), mMaxPageKeyCount);
                 for (int pageId = 0; pageId < sortedKeys.length; ++pageId) {
                     final DynamicGridKeyboard tempKeyboard = new DynamicGridKeyboard(mPrefs,
                             mLayoutSet.getKeyboard(KeyboardId.ELEMENT_EMOJI_RECENTS),
@@ -394,13 +396,13 @@
             }
         };
 
-        private static Key[][] sortKeysIntoPages(final Key[] inKeys, final int maxPageCount) {
-            final Key[] keys = Arrays.copyOf(inKeys, inKeys.length);
-            Arrays.sort(keys, 0, keys.length, EMOJI_KEY_COMPARATOR);
-            final int pageCount = (keys.length - 1) / maxPageCount + 1;
+        private static Key[][] sortKeysIntoPages(final List<Key> inKeys, final int maxPageCount) {
+            final ArrayList<Key> keys = CollectionUtils.newArrayList(inKeys);
+            Collections.sort(keys, EMOJI_KEY_COMPARATOR);
+            final int pageCount = (keys.size() - 1) / maxPageCount + 1;
             final Key[][] retval = new Key[pageCount][maxPageCount];
-            for (int i = 0; i < keys.length; ++i) {
-                retval[i / maxPageCount][i % maxPageCount] = keys[i];
+            for (int i = 0; i < keys.size(); ++i) {
+                retval[i / maxPageCount][i % maxPageCount] = keys.get(i);
             }
             return retval;
         }
diff --git a/java/src/com/android/inputmethod/keyboard/Keyboard.java b/java/src/com/android/inputmethod/keyboard/Keyboard.java
index 4fd3bac..f646a03 100644
--- a/java/src/com/android/inputmethod/keyboard/Keyboard.java
+++ b/java/src/com/android/inputmethod/keyboard/Keyboard.java
@@ -25,6 +25,9 @@
 import com.android.inputmethod.latin.utils.CollectionUtils;
 import com.android.inputmethod.latin.utils.CoordinateUtils;
 
+import java.util.Collections;
+import java.util.List;
+
 /**
  * Loads an XML description of a keyboard and stores the attributes of the keys. A keyboard
  * consists of rows of keys.
@@ -74,10 +77,10 @@
     /** Maximum column for more keys keyboard */
     public final int mMaxMoreKeysKeyboardColumn;
 
-    /** Array of keys and icons in this keyboard */
-    private final Key[] mKeys;
-    public final Key[] mShiftKeys;
-    public final Key[] mAltCodeKeysWhileTyping;
+    /** List of keys in this keyboard */
+    private final List<Key> mSortedKeys;
+    public final List<Key> mShiftKeys;
+    public final List<Key> mAltCodeKeysWhileTyping;
     public final KeyboardIconsSet mIconsSet;
 
     private final SparseArray<Key> mKeyCache = CollectionUtils.newSparseArray();
@@ -100,15 +103,16 @@
         mTopPadding = params.mTopPadding;
         mVerticalGap = params.mVerticalGap;
 
-        mKeys = params.mKeys.toArray(new Key[params.mKeys.size()]);
-        mShiftKeys = params.mShiftKeys.toArray(new Key[params.mShiftKeys.size()]);
-        mAltCodeKeysWhileTyping = params.mAltCodeKeysWhileTyping.toArray(
-                new Key[params.mAltCodeKeysWhileTyping.size()]);
+        mSortedKeys = Collections.unmodifiableList(
+                CollectionUtils.newArrayList(params.mSortedKeys));
+        mShiftKeys = Collections.unmodifiableList(params.mShiftKeys);
+        mAltCodeKeysWhileTyping = Collections.unmodifiableList(params.mAltCodeKeysWhileTyping);
         mIconsSet = params.mIconsSet;
 
         mProximityInfo = new ProximityInfo(params.mId.mLocale.toString(),
                 params.GRID_WIDTH, params.GRID_HEIGHT, mOccupiedWidth, mOccupiedHeight,
-                mMostCommonKeyWidth, mMostCommonKeyHeight, mKeys, params.mTouchPositionCorrection);
+                mMostCommonKeyWidth, mMostCommonKeyHeight, mSortedKeys,
+                params.mTouchPositionCorrection);
         mProximityCharsCorrectionEnabled = params.mProximityCharsCorrectionEnabled;
     }
 
@@ -127,7 +131,7 @@
         mTopPadding = keyboard.mTopPadding;
         mVerticalGap = keyboard.mVerticalGap;
 
-        mKeys = keyboard.mKeys;
+        mSortedKeys = keyboard.mSortedKeys;
         mShiftKeys = keyboard.mShiftKeys;
         mAltCodeKeysWhileTyping = keyboard.mAltCodeKeysWhileTyping;
         mIconsSet = keyboard.mIconsSet;
@@ -152,17 +156,14 @@
         return mProximityInfo;
     }
 
-    public Key[] getKeys() {
-        return mKeys;
-    }
-
-    public Key getKeyFromOutputText(final String outputText) {
-        for (final Key key : getKeys()) {
-            if (outputText.equals(key.getOutputText())) {
-                return key;
-            }
-        }
-        return null;
+    /**
+     * Return the sorted list of keys of this keyboard.
+     * The keys are sorted from top-left to bottom-right order.
+     * The list may contain {@link Spacer} object as well.
+     * @return the sorted unmodifiable list of {@link Key}s of this keyboard.
+     */
+    public List<Key> getSortedKeys() {
+        return mSortedKeys;
     }
 
     public Key getKey(final int code) {
@@ -175,7 +176,7 @@
                 return mKeyCache.valueAt(index);
             }
 
-            for (final Key key : getKeys()) {
+            for (final Key key : getSortedKeys()) {
                 if (key.getCode() == code) {
                     mKeyCache.put(code, key);
                     return key;
@@ -191,7 +192,7 @@
             return true;
         }
 
-        for (final Key key : getKeys()) {
+        for (final Key key : getSortedKeys()) {
             if (key == aKey) {
                 mKeyCache.put(key.getCode(), key);
                 return true;
@@ -209,10 +210,10 @@
      * Returns the array of the keys that are closest to the given point.
      * @param x the x-coordinate of the point
      * @param y the y-coordinate of the point
-     * @return the array of the nearest keys to the given point. If the given
+     * @return the list of the nearest keys to the given point. If the given
      * point is out of range, then an array of size zero is returned.
      */
-    public Key[] getNearestKeys(final int x, final int y) {
+    public List<Key> getNearestKeys(final int x, final int y) {
         // Avoid dead pixels at edges of the keyboard
         final int adjustedX = Math.max(0, Math.min(x, mOccupiedWidth - 1));
         final int adjustedY = Math.max(0, Math.min(y, mOccupiedHeight - 1));
diff --git a/java/src/com/android/inputmethod/keyboard/KeyboardView.java b/java/src/com/android/inputmethod/keyboard/KeyboardView.java
index 18e51d3..8ca00b0 100644
--- a/java/src/com/android/inputmethod/keyboard/KeyboardView.java
+++ b/java/src/com/android/inputmethod/keyboard/KeyboardView.java
@@ -289,7 +289,7 @@
         // TODO: Confirm if it's really required to draw all keys when hardware acceleration is on.
         if (drawAllKeys || isHardwareAccelerated) {
             // Draw all keys.
-            for (final Key key : mKeyboard.getKeys()) {
+            for (final Key key : mKeyboard.getSortedKeys()) {
                 onDrawKey(key, canvas, paint);
             }
         } else {
diff --git a/java/src/com/android/inputmethod/keyboard/MoreKeysDetector.java b/java/src/com/android/inputmethod/keyboard/MoreKeysDetector.java
index abff202..5a9d475 100644
--- a/java/src/com/android/inputmethod/keyboard/MoreKeysDetector.java
+++ b/java/src/com/android/inputmethod/keyboard/MoreKeysDetector.java
@@ -43,7 +43,7 @@
 
         Key nearestKey = null;
         int nearestDist = (y < 0) ? mSlideAllowanceSquareTop : mSlideAllowanceSquare;
-        for (final Key key : keyboard.getKeys()) {
+        for (final Key key : keyboard.getSortedKeys()) {
             final int dist = key.squaredDistanceToEdge(touchX, touchY);
             if (dist < nearestDist) {
                 nearestKey = key;
diff --git a/java/src/com/android/inputmethod/keyboard/ProximityInfo.java b/java/src/com/android/inputmethod/keyboard/ProximityInfo.java
index a031669..3746d5b 100644
--- a/java/src/com/android/inputmethod/keyboard/ProximityInfo.java
+++ b/java/src/com/android/inputmethod/keyboard/ProximityInfo.java
@@ -22,9 +22,13 @@
 
 import com.android.inputmethod.keyboard.internal.TouchPositionCorrection;
 import com.android.inputmethod.latin.Constants;
+import com.android.inputmethod.latin.utils.CollectionUtils;
 import com.android.inputmethod.latin.utils.JniUtils;
 
+import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
 
 public class ProximityInfo {
     private static final String TAG = ProximityInfo.class.getSimpleName();
@@ -34,7 +38,7 @@
     public static final int MAX_PROXIMITY_CHARS_SIZE = 16;
     /** Number of key widths from current touch point to search for nearest keys. */
     private static final float SEARCH_DISTANCE = 1.2f;
-    private static final Key[] EMPTY_KEY_ARRAY = new Key[0];
+    private static final List<Key> EMPTY_KEY_LIST = Collections.emptyList();
     private static final float DEFAULT_TOUCH_POSITION_CORRECTION_RADIUS = 0.15f;
 
     private final int mGridWidth;
@@ -47,13 +51,13 @@
     private final int mKeyboardHeight;
     private final int mMostCommonKeyWidth;
     private final int mMostCommonKeyHeight;
-    private final Key[] mKeys;
-    private final Key[][] mGridNeighbors;
+    private final List<Key> mSortedKeys;
+    private final List<Key>[] mGridNeighbors;
     private final String mLocaleStr;
 
     ProximityInfo(final String localeStr, final int gridWidth, final int gridHeight,
             final int minWidth, final int height, final int mostCommonKeyWidth,
-            final int mostCommonKeyHeight, final Key[] keys,
+            final int mostCommonKeyHeight, final List<Key> sortedKeys,
             final TouchPositionCorrection touchPositionCorrection) {
         if (TextUtils.isEmpty(localeStr)) {
             mLocaleStr = "";
@@ -69,8 +73,8 @@
         mKeyboardHeight = height;
         mMostCommonKeyHeight = mostCommonKeyHeight;
         mMostCommonKeyWidth = mostCommonKeyWidth;
-        mKeys = keys;
-        mGridNeighbors = new Key[mGridSize][];
+        mSortedKeys = sortedKeys;
+        mGridNeighbors = new List[mGridSize];
         if (minWidth == 0 || height == 0) {
             // No proximity required. Keyboard might be more keys keyboard.
             return;
@@ -99,7 +103,7 @@
         return key.getCode() >= Constants.CODE_SPACE;
     }
 
-    private static int getProximityInfoKeysCount(final Key[] keys) {
+    private static int getProximityInfoKeysCount(final List<Key> keys) {
         int count = 0;
         for (final Key key : keys) {
             if (needsProximityInfo(key)) {
@@ -110,14 +114,14 @@
     }
 
     private long createNativeProximityInfo(final TouchPositionCorrection touchPositionCorrection) {
-        final Key[][] gridNeighborKeys = mGridNeighbors;
+        final List<Key>[] gridNeighborKeys = mGridNeighbors;
         final int[] proximityCharsArray = new int[mGridSize * MAX_PROXIMITY_CHARS_SIZE];
         Arrays.fill(proximityCharsArray, Constants.NOT_A_CODE);
         for (int i = 0; i < mGridSize; ++i) {
-            final int proximityCharsLength = gridNeighborKeys[i].length;
+            final int proximityCharsLength = gridNeighborKeys[i].size();
             int infoIndex = i * MAX_PROXIMITY_CHARS_SIZE;
             for (int j = 0; j < proximityCharsLength; ++j) {
-                final Key neighborKey = gridNeighborKeys[i][j];
+                final Key neighborKey = gridNeighborKeys[i].get(j);
                 // Excluding from proximityCharsArray
                 if (!needsProximityInfo(neighborKey)) {
                     continue;
@@ -142,8 +146,8 @@
             }
         }
 
-        final Key[] keys = mKeys;
-        final int keyCount = getProximityInfoKeysCount(keys);
+        final List<Key> sortedKeys = mSortedKeys;
+        final int keyCount = getProximityInfoKeysCount(sortedKeys);
         final int[] keyXCoordinates = new int[keyCount];
         final int[] keyYCoordinates = new int[keyCount];
         final int[] keyWidths = new int[keyCount];
@@ -153,8 +157,8 @@
         final float[] sweetSpotCenterYs;
         final float[] sweetSpotRadii;
 
-        for (int infoIndex = 0, keyIndex = 0; keyIndex < keys.length; keyIndex++) {
-            final Key key = keys[keyIndex];
+        for (int infoIndex = 0, keyIndex = 0; keyIndex < sortedKeys.size(); keyIndex++) {
+            final Key key = sortedKeys.get(keyIndex);
             // Excluding from key coordinate arrays
             if (!needsProximityInfo(key)) {
                 continue;
@@ -177,8 +181,8 @@
             final int rows = touchPositionCorrection.getRows();
             final float defaultRadius = DEFAULT_TOUCH_POSITION_CORRECTION_RADIUS
                     * (float)Math.hypot(mMostCommonKeyWidth, mMostCommonKeyHeight);
-            for (int infoIndex = 0, keyIndex = 0; keyIndex < keys.length; keyIndex++) {
-                final Key key = keys[keyIndex];
+            for (int infoIndex = 0, keyIndex = 0; keyIndex < sortedKeys.size(); keyIndex++) {
+                final Key key = sortedKeys.get(keyIndex);
                 // Excluding from touch position correction arrays
                 if (!needsProximityInfo(key)) {
                     continue;
@@ -240,7 +244,7 @@
 
     private void computeNearestNeighbors() {
         final int defaultWidth = mMostCommonKeyWidth;
-        final int keyCount = mKeys.length;
+        final int keyCount = mSortedKeys.size();
         final int gridSize = mGridNeighbors.length;
         final int threshold = (int) (defaultWidth * SEARCH_DISTANCE);
         final int thresholdSquared = threshold * threshold;
@@ -259,7 +263,7 @@
         final int[] neighborCountPerCell = new int[gridSize];
         final int halfCellWidth = mCellWidth / 2;
         final int halfCellHeight = mCellHeight / 2;
-        for (final Key key : mKeys) {
+        for (final Key key : mSortedKeys) {
             if (key.isSpacer()) continue;
 
 /* HOW WE PRE-SELECT THE CELLS (iterate over only the relevant cells, instead of all of them)
@@ -353,9 +357,13 @@
         }
 
         for (int i = 0; i < gridSize; ++i) {
-            final int base = i * keyCount;
-            mGridNeighbors[i] =
-                    Arrays.copyOfRange(neighborsFlatBuffer, base, base + neighborCountPerCell[i]);
+            final int indexStart = i * keyCount;
+            final int indexEnd = indexStart + neighborCountPerCell[i];
+            final ArrayList<Key> neighbords = CollectionUtils.newArrayList(indexEnd - indexStart);
+            for (int index = indexStart; index < indexEnd; index++) {
+                neighbords.add(neighborsFlatBuffer[index]);
+            }
+            mGridNeighbors[i] = Collections.unmodifiableList(neighbords);
         }
     }
 
@@ -369,7 +377,7 @@
         if (primaryKeyCode > Constants.CODE_SPACE) {
             dest[index++] = primaryKeyCode;
         }
-        final Key[] nearestKeys = getNearestKeys(x, y);
+        final List<Key> nearestKeys = getNearestKeys(x, y);
         for (Key key : nearestKeys) {
             if (index >= destLength) {
                 break;
@@ -385,9 +393,9 @@
         }
     }
 
-    public Key[] getNearestKeys(final int x, final int y) {
+    public List<Key> getNearestKeys(final int x, final int y) {
         if (mGridNeighbors == null) {
-            return EMPTY_KEY_ARRAY;
+            return EMPTY_KEY_LIST;
         }
         if (x >= 0 && x < mKeyboardMinWidth && y >= 0 && y < mKeyboardHeight) {
             int index = (y / mCellHeight) * mGridWidth + (x / mCellWidth);
@@ -395,6 +403,6 @@
                 return mGridNeighbors[index];
             }
         }
-        return EMPTY_KEY_ARRAY;
+        return EMPTY_KEY_LIST;
     }
 }
diff --git a/java/src/com/android/inputmethod/keyboard/internal/DynamicGridKeyboard.java b/java/src/com/android/inputmethod/keyboard/internal/DynamicGridKeyboard.java
index e2fd390..397c098 100644
--- a/java/src/com/android/inputmethod/keyboard/internal/DynamicGridKeyboard.java
+++ b/java/src/com/android/inputmethod/keyboard/internal/DynamicGridKeyboard.java
@@ -30,6 +30,7 @@
 import java.util.ArrayDeque;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Collections;
 import java.util.List;
 
 /**
@@ -50,7 +51,7 @@
     private final ArrayDeque<GridKey> mGridKeys = CollectionUtils.newArrayDeque();
     private final ArrayDeque<Key> mPendingKeys = CollectionUtils.newArrayDeque();
 
-    private Key[] mCachedGridKeys;
+    private List<Key> mCachedGridKeys;
 
     public DynamicGridKeyboard(final SharedPreferences prefs, final Keyboard templateKeyboard,
             final int maxKeyCount, final int categoryId) {
@@ -66,7 +67,7 @@
     }
 
     private Key getTemplateKey(final int code) {
-        for (final Key key : super.getKeys()) {
+        for (final Key key : super.getSortedKeys()) {
             if (key.getCode() == code) {
                 return key;
             }
@@ -146,9 +147,10 @@
     private static Key getKeyByCode(final Collection<DynamicGridKeyboard> keyboards,
             final int code) {
         for (final DynamicGridKeyboard keyboard : keyboards) {
-            final Key key = keyboard.getKey(code);
-            if (key != null) {
-                return key;
+            for (final Key key : keyboard.getSortedKeys()) {
+                if (key.getCode() == code) {
+                    return key;
+                }
             }
         }
         return null;
@@ -156,10 +158,11 @@
 
     private static Key getKeyByOutputText(final Collection<DynamicGridKeyboard> keyboards,
             final String outputText) {
-        for (final DynamicGridKeyboard kbd : keyboards) {
-            final Key key = kbd.getKeyFromOutputText(outputText);
-            if (key != null) {
-                return key;
+        for (final DynamicGridKeyboard keyboard : keyboards) {
+            for (final Key key : keyboard.getSortedKeys()) {
+                if (outputText.equals(key.getOutputText())) {
+                    return key;
+                }
             }
         }
         return null;
@@ -205,20 +208,22 @@
     }
 
     @Override
-    public Key[] getKeys() {
+    public List<Key> getSortedKeys() {
         synchronized (mLock) {
             if (mCachedGridKeys != null) {
                 return mCachedGridKeys;
             }
-            mCachedGridKeys = mGridKeys.toArray(new Key[mGridKeys.size()]);
+            final ArrayList<Key> cachedKeys = CollectionUtils.newArrayList(mGridKeys.size());
+            cachedKeys.addAll(mGridKeys);
+            mCachedGridKeys = Collections.unmodifiableList(cachedKeys);
             return mCachedGridKeys;
         }
     }
 
     @Override
-    public Key[] getNearestKeys(final int x, final int y) {
+    public List<Key> getNearestKeys(final int x, final int y) {
         // TODO: Calculate the nearest key index in mGridKeys from x and y.
-        return getKeys();
+        return getSortedKeys();
     }
 
     static final class GridKey extends Key {
diff --git a/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java b/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java
index 153391e..a61a79b 100644
--- a/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java
+++ b/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java
@@ -24,6 +24,8 @@
 import com.android.inputmethod.latin.utils.CollectionUtils;
 
 import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.SortedSet;
 import java.util.TreeSet;
 
 public class KeyboardParams {
@@ -58,7 +60,8 @@
     public int GRID_WIDTH;
     public int GRID_HEIGHT;
 
-    public final TreeSet<Key> mKeys = CollectionUtils.newTreeSet(); // ordered set
+    // Keys are sorted from top-left to bottom-right order.
+    public final SortedSet<Key> mSortedKeys = new TreeSet<Key>(ROW_COLUMN_COMPARATOR);
     public final ArrayList<Key> mShiftKeys = CollectionUtils.newArrayList();
     public final ArrayList<Key> mAltCodeKeysWhileTyping = CollectionUtils.newArrayList();
     public final KeyboardIconsSet mIconsSet = new KeyboardIconsSet();
@@ -75,8 +78,20 @@
     public final TouchPositionCorrection mTouchPositionCorrection =
             new TouchPositionCorrection();
 
+    // Comparator to sort {@link Key}s from top-left to bottom-right order.
+    private static final Comparator<Key> ROW_COLUMN_COMPARATOR = new Comparator<Key>() {
+        @Override
+        public int compare(final Key lhs, final Key rhs) {
+            if (lhs.getY() < rhs.getY()) return -1;
+            if (lhs.getY() > rhs.getY()) return 1;
+            if (lhs.getX() < rhs.getX()) return -1;
+            if (lhs.getX() > rhs.getX()) return 1;
+            return 0;
+        }
+    };
+
     protected void clearKeys() {
-        mKeys.clear();
+        mSortedKeys.clear();
         mShiftKeys.clear();
         clearHistogram();
     }
@@ -88,7 +103,7 @@
             // Ignore zero width {@link Spacer}.
             return;
         }
-        mKeys.add(key);
+        mSortedKeys.add(key);
         if (isSpacer) {
             return;
         }
diff --git a/java/src/com/android/inputmethod/latin/BinaryDictionary.java b/java/src/com/android/inputmethod/latin/BinaryDictionary.java
index 88174ba..38359fc 100644
--- a/java/src/com/android/inputmethod/latin/BinaryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/BinaryDictionary.java
@@ -460,6 +460,7 @@
                 dictFile.length(), mIsUpdatable);
     }
 
+    // Flush to dict file if the dictionary has been updated.
     public void flush() {
         if (!isValidDictionary()) return;
         if (mHasUpdated) {
@@ -468,6 +469,14 @@
         }
     }
 
+    // Run GC and flush to dict file if the dictionary has been updated.
+    public void flushWithGCIfHasUpdated() {
+        if (mHasUpdated) {
+            flushWithGC();
+        }
+    }
+
+    // Run GC and flush to dict file.
     public void flushWithGC() {
         if (!isValidDictionary()) return;
         flushWithGCNative(mNativeDict, mDictFilePath);
diff --git a/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java b/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
index 64e9d2b..a6a7354 100644
--- a/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
@@ -515,7 +515,8 @@
         createBinaryDictionaryLocked();
         openBinaryDictionaryLocked();
         loadInitialContentsLocked();
-        mBinaryDictionary.flushWithGC();
+        // Run GC and flush to file when initial contents have been loaded.
+        mBinaryDictionary.flushWithGCIfHasUpdated();
     }
 
     private void flushDictionaryLocked() {
diff --git a/java/src/com/android/inputmethod/research/ResearchLogger.java b/java/src/com/android/inputmethod/research/ResearchLogger.java
index b1f54c0..d907dd1 100644
--- a/java/src/com/android/inputmethod/research/ResearchLogger.java
+++ b/java/src/com/android/inputmethod/research/ResearchLogger.java
@@ -1362,7 +1362,7 @@
                 kid.navigateNext(), kid.navigatePrevious(), kid.mClobberSettingsKey,
                 isPasswordView, kid.mSupportsSwitchingToShortcutIme, kid.mHasShortcutKey,
                 kid.mLanguageSwitchKeyEnabled, kid.isMultiLine(), keyboard.mOccupiedWidth,
-                keyboard.mOccupiedHeight, keyboard.getKeys());
+                keyboard.mOccupiedHeight, keyboard.getSortedKeys());
     }
 
     /**
diff --git a/tests/src/com/android/inputmethod/keyboard/layout/expected/ActualKeyboardBuilder.java b/tests/src/com/android/inputmethod/keyboard/layout/expected/ActualKeyboardBuilder.java
index 050bc4c..26d2e2a 100644
--- a/tests/src/com/android/inputmethod/keyboard/layout/expected/ActualKeyboardBuilder.java
+++ b/tests/src/com/android/inputmethod/keyboard/layout/expected/ActualKeyboardBuilder.java
@@ -24,26 +24,13 @@
 import com.android.inputmethod.latin.utils.StringUtils;
 
 import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
+import java.util.List;
 
 /**
  * This class builds an actual keyboard for unit test.
  */
 public final class ActualKeyboardBuilder extends AbstractKeyboardBuilder<Key> {
-    // Comparator to sort {@link Key}s from top-left to bottom-right order.
-    private static final Comparator<Key> ROW_COLUMN_COMPARATOR = new Comparator<Key>() {
-        @Override
-        public int compare(final Key lhs, final Key rhs) {
-            if (lhs.getY() < rhs.getY()) return -1;
-            if (lhs.getY() > rhs.getY()) return 1;
-            if (lhs.getX() < rhs.getX()) return -1;
-            if (lhs.getX() > rhs.getX()) return 1;
-            return 0;
-        }
-    };
-
-    private static ArrayList<Key> filterOutSpacerAndSortKeys(final Key[] keys) {
+    private static ArrayList<Key> filterOutSpacer(final List<Key> keys) {
         final ArrayList<Key> filteredKeys = CollectionUtils.newArrayList();
         for (final Key key : keys) {
             if (key.isSpacer()) {
@@ -51,25 +38,23 @@
             }
             filteredKeys.add(key);
         }
-        Collections.sort(filteredKeys, ROW_COLUMN_COMPARATOR);
         return filteredKeys;
     }
 
     /**
      * Create the keyboard that consists of the array of rows of the actual keyboard's keys.
-     * @param keys the array of keys of the actual keyboard.
+     * @param sortedKeys the sorted list of keys of the actual keyboard.
      * @return the actual keyboard grouped with rows.
      */
-    public static Key[][] buildKeyboard(final Key[] keys) {
-        // Filter out spacer and sort keys from top-left to bottom-right order to prepare to
-        // create rows.
-        final ArrayList<Key> sortedKeys = filterOutSpacerAndSortKeys(keys);
+    public static Key[][] buildKeyboard(final List<Key> sortedKeys) {
+        // Filter out spacer to prepare to create rows.
+        final ArrayList<Key> filteredSortedKeys = filterOutSpacer(sortedKeys);
 
         // Grouping keys into rows.
         final ArrayList<ArrayList<Key>> rows = CollectionUtils.newArrayList();
         ArrayList<Key> elements = CollectionUtils.newArrayList();
-        int lastY = sortedKeys.get(0).getY();
-        for (final Key key : sortedKeys) {
+        int lastY = filteredSortedKeys.get(0).getY();
+        for (final Key key : filteredSortedKeys) {
             if (lastY != key.getY()) {
                 // A new row is starting.
                 lastY = key.getY();
diff --git a/tests/src/com/android/inputmethod/keyboard/layout/tests/LayoutTestsBase.java b/tests/src/com/android/inputmethod/keyboard/layout/tests/LayoutTestsBase.java
index 555ec89..4002c49 100644
--- a/tests/src/com/android/inputmethod/keyboard/layout/tests/LayoutTestsBase.java
+++ b/tests/src/com/android/inputmethod/keyboard/layout/tests/LayoutTestsBase.java
@@ -150,7 +150,8 @@
         // Create actual keyboard object.
         final Keyboard keyboard = mKeyboardLayoutSet.getKeyboard(elementId);
         // Create actual keyboard to be compared with the expected keyboard.
-        final Key[][] actualKeyboard = ActualKeyboardBuilder.buildKeyboard(keyboard.getKeys());
+        final Key[][] actualKeyboard = ActualKeyboardBuilder.buildKeyboard(
+                keyboard.getSortedKeys());
 
         // Dump human readable definition of expected/actual keyboards.
         Log.d(tag, "expected=\n" + ExpectedKeyboardBuilder.toString(expectedKeyboard));