You should be able to use regular expressions to extract the hour, minute, second, and ms values from the time stamps and then convert the extracted values to seconds:
% Create cell array containing time stampes
timestamps = {'00:20.360','00:39.132','00:40.360','00:49.259','00:59.508','111:59:11.360'};
% Extract time stamp parts; hour, minute, second, and fraction will be stored in a structure array
parse = regexp(timestamps, ...
'(?<hour>\d+)?:?(?<minute>\d+):(?<second>\d+)\.(?<fraction>\d+)', 'names', 'once');
parse = cat(1, parse{:});
% Convert the structure array into a regular matrix with hours in the first row, minutes
% in the second row, seconds in the third row, and ms in the fourth row:
parts = str2double(struct2cell(parse));
% Use matrix multiplication to calculate the total value (in seconds) of each timestamp
in_secs = [3600, 60, 1, 0.001] * parts;
% Then plot the data:
plot(in_secs, values);
