diff --git a/include/freetype/internal/tttypes.h b/include/freetype/internal/tttypes.h
index fcd97cf..286f14f 100644
--- a/include/freetype/internal/tttypes.h
+++ b/include/freetype/internal/tttypes.h
@@ -1390,8 +1390,8 @@
    *   hdmx_record_size ::
    *     The size of a single hdmx record.
    *
-   *   hdmx_record_sizes ::
-   *     An array holding the ppem sizes available in the 'hdmx' table.
+   *   hdmx_records ::
+   *     A array of pointers to the 'hdmx' table records sorted by ppem.
    *
    *   sbit_table ::
    *     A pointer to the font's embedded bitmap location table.
@@ -1605,7 +1605,7 @@
     FT_ULong              hdmx_table_size;
     FT_UInt               hdmx_record_count;
     FT_ULong              hdmx_record_size;
-    FT_Byte*              hdmx_record_sizes;
+    FT_Byte**             hdmx_records;
 
     FT_Byte*              sbit_table;
     FT_ULong              sbit_table_size;
diff --git a/src/truetype/ttpload.c b/src/truetype/ttpload.c
index 71db75a..3c9b00a 100644
--- a/src/truetype/ttpload.c
+++ b/src/truetype/ttpload.c
@@ -498,6 +498,14 @@
   }
 
 
+  FT_COMPARE_DEF( int )
+  compare_ppem( const void*  a,
+                const void*  b )
+  {
+    return **(FT_Byte**)a - **(FT_Byte**)b;
+  }
+
+
   /**************************************************************************
    *
    * @Function:
@@ -574,20 +582,21 @@
       goto Fail;
     }
 
-    if ( FT_QNEW_ARRAY( face->hdmx_record_sizes, num_records ) )
+    if ( FT_QNEW_ARRAY( face->hdmx_records, num_records ) )
       goto Fail;
 
-    /* XXX: We do not check if the records are sorted by ppem */
-    /* and cannot use binary search later.                    */
     for ( nn = 0; nn < num_records; nn++ )
     {
       if ( p + record_size > limit )
         break;
-
-      face->hdmx_record_sizes[nn] = p[0];
-      p                          += record_size;
+      face->hdmx_records[nn] = p;
+      p                     += record_size;
     }
 
+    /* The records must be already sorted by ppem but it does not */
+    /* hurt to make sure so that the binary search works later.   */
+    ft_qsort( face->hdmx_records, nn, sizeof ( FT_Byte* ), compare_ppem );
+
     face->hdmx_record_count = nn;
     face->hdmx_table_size   = table_size;
     face->hdmx_record_size  = record_size;
@@ -611,7 +620,7 @@
     FT_Memory  memory = stream->memory;
 
 
-    FT_FREE( face->hdmx_record_sizes );
+    FT_FREE( face->hdmx_records );
     FT_FRAME_RELEASE( face->hdmx_table );
   }
 
@@ -619,27 +628,34 @@
   /**************************************************************************
    *
    * Return the advance width table for a given pixel size if it is found
-   * in the font's `hdmx' table (if any).
+   * in the font's `hdmx' table (if any).  The records must be sorted for
+   * the binary search to work properly.
    */
   FT_LOCAL_DEF( FT_Byte* )
   tt_face_get_device_metrics( TT_Face  face,
                               FT_UInt  ppem,
                               FT_UInt  gindex )
   {
-    FT_UInt   nn;
-    FT_Byte*  result      = NULL;
-    FT_ULong  record_size = face->hdmx_record_size;
-    FT_Byte*  record      = FT_OFFSET( face->hdmx_table, 8 );
+    FT_UInt   min    = 0;
+    FT_UInt   max    = face->hdmx_record_count;
+    FT_UInt   mid;
+    FT_Byte*  result = NULL;
 
 
-    for ( nn = 0; nn < face->hdmx_record_count; nn++ )
-      if ( face->hdmx_record_sizes[nn] == ppem )
+    while ( min < max )
+    {
+      mid = ( min + max ) >> 1;
+
+      if ( face->hdmx_records[mid][0] > ppem )
+        max = mid;
+      else if ( face->hdmx_records[mid][0] < ppem )
+        min = mid + 1;
+      else
       {
-        gindex += 2;
-        if ( gindex < record_size )
-          result = record + nn * record_size + gindex;
+        result = face->hdmx_records[mid] + 2 + gindex;
         break;
       }
+    }
 
     return result;
   }