A time scaler (200; 340; 450; 866; 900; 1000) for providing a time scaled version (212;312;448;956) of an input audio signal (210; 332;442;910), wherein the time scaler is configured to compute or estimate (950; 1060) a quality (q) of a time scaled version of the input audio signal obtainable by a time scaling of the input audio signal, and wherein the time scaler is configured to perform (954;1068) the time scaling of the input audio signal in dependence on the computation or estimation of the quality (q) of the time scaled version of the input audio signal obtainable by the time scaling; wherein the time scaler is configured to time-shift a second block of samples with respect to a first block of samples by a time-shift (p), and to overlap-and-add (954;1068) the first block of samples and the time-shifted second block of samples, to thereby obtain the time-scaled version of the input audio signal, if the computation or estimation of the quality (q) of the time scaled version of the input audio signal obtainable by the time scaling indicates a quality which is larger than or equal to a quality threshold value (qmin); and wherein the time scaler is configured to determine the time shift (p) of the second block of samples with respect to the first block of samples in dependence on a determination of a level of similarity, evaluated using a first similarity measure, between the first block of samples, or a portion of the first block of samples, and the second block of samples, or a portion of the second block of samples, wherein the determined time shift (p) is an information describing a position of highest similarity; wherein the time scaler is configured to compute or estimate (950;1060) the quality (q) of the time scaled version of the input audio signal obtainable by the time scaling of the input audio signal on the basis of an information about the level of similarity between the first block of samples, or a portion of the first block of samples, and the second block of samples, time-shifted by the determined time shift (p), or a portion of the second block of samples, time-shifted by the determined time shift (p), characterized in that the information about the level of similarity between the first block of samples, or a portion of the first block of samples, and the second block of samples, time-shifted by the determined time shift (p), or a portion of the second block of samples, time-shifted by the determined time shift (p), is evaluated using a second similarity measure that is obtained based on the determined time-shift (p). wherein the time scaler is configured to compute or estimate (950; 1060) a quality (q) of a time scaled version of the input audio signal obtainable by a time scaling of the input audio signal, and wherein the time scaler is configured to perform (954;1068) the time scaling of the input audio signal in dependence on the computation or estimation of the quality (q) of the time scaled version of the input audio signal obtainable by the time scaling; wherein the time scaler is configured to time-shift a second block of samples with respect to a first block of samples by a time-shift (p), and to overlap-and-add (954;1068) the first block of samples and the time-shifted second block of samples, to thereby obtain the time-scaled version of the input audio signal, if the computation or estimation of the quality (q) of the time scaled version of the input audio signal obtainable by the time scaling indicates a quality which is larger than or equal to a quality threshold value (qmin); and wherein the time scaler is configured to determine the time shift (p) of the second block of samples with respect to the first block of samples in dependence on a determination of a level of similarity, evaluated using a first similarity measure, between the first block of samples, or a portion of the first block of samples, and the second block of samples, or a portion of the second block of samples, wherein the determined time shift (p) is an information describing a position of highest similarity; wherein the time scaler is configured to compute or estimate (950;1060) the quality (q) of the time scaled version of the input audio signal obtainable by the time scaling of the input audio signal on the basis of an information about the level of similarity between the first block of samples, or a portion of the first block of samples, and the second block of samples, time-shifted by the determined time shift (p), or a portion of the second block of samples, time-shifted by the determined time shift (p), characterized in that the information about the level of similarity between the first block of samples, or a portion of the first block of samples, and the second block of samples, time-shifted by the determined time shift (p), or a portion of the second block of samples, time-shifted by the determined time shift (p), is evaluated using a second similarity measure that is obtained based on the determined time-shift (p).