Implementation of Optical Frequency Domain Reflectometry (OFDR) requires a source whose instantaneous frequency can be accurately scanned over a sufficiently wide frequency range. Achieving high repetition rates of accurate linear frequency sweeps can be rather challenging. In contrast, fast and accurate Sinusoidal Frequency Scan (SFS-OFDR) can be easily implemented via direct or external optical frequency modulation. While enabling high spatial resolution measurements of a sensing fiber at high scan rates, SFS-OFDR requires a special processing algorithm to convert the detector output to fiber profiles. Previous implementation of the algorithm involved O (N2) complexity and prohibited real time operation. In this work a novel algorithm for processing SFS-OFDR raw data is introduced. Based on two consecutive FFT operations, the algorithm produces the fiber profile with O (N log N) operations and lends itself for real time-applications. The new method was tested via simulation and experiment. It enabled static detection with high resolution (∼3m) at 64km and highly sensitive dynamic detection (stretching amplitude of 70nm) near the end of a 64km sensing fiber with spatial resolution <10m and with 400Hz scan repetition rate.