Why index is not used with order by? I trying to get info about why MySQL does not using my index when I create a inner join and trying to ORDER BY on the end.

I have my SQL query here:

SELECT
    *           
FROM
    product p INNER JOIN productStore ps ON p.productUUID = ps.productUUID       
ORDER BY
    ps.storeTitle 
LIMIT 50;


When I'm using order by this select take over 3,5 sec, when i remove order by its taking like 1,6ms to run the same SQL, my explain SQL is follow

With ORDER BY:

id  select_type table   type    possible_keys   key key_len ref rows    Extra
1   SIMPLE  ps  ALL PRIMARY NULL    NULL    NULL    942187  Using filesort
1   SIMPLE  p   eq_ref  PRIMARY PRIMARY 16  foeniks_core.ps.productUUID 1   NULL


Without ORDER BY:

id  select_type table   type    possible_keys   key key_len ref rows    Extra
1   SIMPLE  ps  ALL PRIMARY NULL    NULL    NULL    942187  NULL
1   SIMPLE  p   eq_ref  PRIMARY PRIMARY 16  foeniks_core.ps.productUUID 1   NULL


the field there not are indexing right is a varchar on 282 length.

My table design is here:

CREATE TABLE `productStore` (
  `productUUID` binary(16) NOT NULL,
  `storeUUID` binary(16) NOT NULL,
  `distributorLastUsed` binary(16) DEFAULT NULL,
  `storeTitle` varchar(282) DEFAULT NULL,
  `storeUrl` varchar(282) DEFAULT NULL,
  `storeDescription` text,
  `storeDescriptionDemo` text,
  `storePrice` int(11) NOT NULL DEFAULT '0',
  `storePriceNext` int(11) NOT NULL DEFAULT '0',
  `storePriceCost` int(11) NOT NULL DEFAULT '0',
  `overwrites` int(11) NOT NULL DEFAULT '0',
  `updated` datetime NOT NULL DEFAULT '1000-01-01 00:00:00',
  `added` datetime NOT NULL DEFAULT '1000-01-01 00:00:00',
  `allowDisplay` tinyint(1) NOT NULL DEFAULT '0',
  `activated` tinyint(1) NOT NULL DEFAULT '1',
  PRIMARY KEY (`productUUID`,`storeUUID`),
  KEY `productStoreLanguageToStore_idx` (`storeUUID`),
  KEY `productStoreToDistributor_idx` (`distributorLastUsed`),
  KEY `storeUrl` (`storeUrl`(180)) USING BTREE,
  KEY `testStoreTitle` (`storeTitle`(182)),
  CONSTRAINT `productStoreToDistributor` FOREIGN KEY (`distributorLastUsed`) REFERENCES `distributor` (`distributorUUID`) ON DELETE SET NULL ON UPDATE CASCADE,
  CONSTRAINT `productStoreToProduct` FOREIGN KEY (`productUUID`) REFERENCES `product` (`productUUID`) ON DELETE CASCADE ON UPDATE CASCADE,
  CONSTRAINT `productStoreToStore` FOREIGN KEY (`storeUUID`) REFERENCES `store` (`storeUUID`) ON DELETE CASCADE ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;


Product table:

CREATE TABLE `product` (
  `productUUID` binary(16) NOT NULL,
  `productManufacturerUUID` binary(16) NOT NULL,
  `productManufacturerSKU` varchar(40) DEFAULT NULL,
  `productEan` varchar(40) DEFAULT NULL,
  `cnetID` varchar(10) DEFAULT NULL,
  `edbID` int(10) DEFAULT NULL,
  `overwrites` int(10) NOT NULL DEFAULT '0',
  `updated` datetime NOT NULL DEFAULT '1000-01-01 00:00:00',
  `added` datetime NOT NULL DEFAULT '1000-01-01 00:00:00',
  `activated` tinyint(1) NOT NULL DEFAULT '1',
  PRIMARY KEY (`productUUID`),
  KEY `manufacturerSKU` (`productManufacturerSKU`(16)),
  KEY `productToManufacturer_idx` (`productManufacturerUUID`),
  KEY `cnetID` (`cnetID`),
  KEY `productEAN` (`productEan`),
  CONSTRAINT `productToManufacturer` FOREIGN KEY (`productManufacturerUUID`) REFERENCES `manufacturer` (`manufacturerUUID`) ON DELETE NO ACTION ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
David Spillett's answer is correct in all points, except for the "encouraging" suggestion.

Here's a way to not only encourage but (in almost all versions) force the optimizer to choose a plan that uses the wanted index to find the 50 rows - and only after that perform the join. It can't always be used but the FOREIGN KEY constraint assures that in this case the two queries will produce identical results.
I call this technique "first LIMIT, then JOIN":

SELECT     p.*, ps.*           
FROM       ( SELECT     *
             FROM       productStore 
             ORDER BY   storeTitle 
             LIMIT 50 
           ) ps 
    INNER JOIN product p 
        ON p.productUUID = ps.productUUID       
ORDER BY   ps.storeTitle ;