You need to reduce the \linewidth before using \lstinputlisting, otherwise it uses the full normal line width.
You can do this using \parbox or minipage environment. For example the following code places the listing in a paragraph box with 48% of the normal line width. (Some people use \textwidth which is mostly the same.)
\parbox{.48\linewidth}{\lstinputlisting{file.c}}
The reason why your first example doesn't work is that lstlisting is a verbatim environment and therefore not allowed in arguments of other macros. This is because the code is read as part of the argument before \begin{lstlisting} is processed and tells LaTeX to thread the code verbatim!
If you want to have the code in the main file, you could store the listings in a box which is then used in the \subfloat. This requires minipage because \parbox would also read the listing as macro argument.
\documentclass{article}
\usepackage{xcolor}
\usepackage{subfig}
\usepackage{listings}
\lstset{%
language=C,
frame=single,
numbers=left,
numberstyle=\footnotesize,
tabsize=2,
keepspaces=true,
columns=fullflexible,
basicstyle=\ttfamily\scriptsize,
keywordstyle=\color{blue}
}
\newsavebox{\mylistingbox}
\begin{document}
\begin{figure}
\begin{lrbox}{\mylistingbox}%
\begin{minipage}{.45\linewidth}%
\begin{lstlisting}
for(int i = 0 ; i < N ; i++)
for(int j = 0 ; j < N ; j++)
for(int k = 0 ; k < N ; k++)
c[i][j] += a[i][k] * b[k][j];
\end{lstlisting}%
\end{minipage}%
\end{lrbox}%
%
\subfloat[small code]{\usebox{\mylistingbox}}%
%
\hfill
%
\begin{lrbox}{\mylistingbox}%
\begin{minipage}{.45\linewidth}%
\begin{lstlisting}
for(int ii = 0 ; ii < N ; ii+=B) {
for(int jj = 0 ; jj < N ; jj+=B) {
for(int kk = 0 ; kk < N ; kk+=B) {
for(int i = ii ; i < ii + B ; i++) {
for(int k = kk ; k < kk + B ; k++){
c_i = c[i];
a_ik = a[i][k];
b_k = b[k];
for(int j = jj ; j < jj + B ; j+=2){
c_i[j] += a_ik * b_k[j];
c_i[j+1] += a_ik * b_k[j+1];
}
}
}
}
}
}
\end{lstlisting}%
\end{minipage}%
\end{lrbox}%
%
\subfloat[Larger code]{\usebox{\mylistingbox}}%
\end{figure}
\end{document}
I reduces the font size here to fit both on the normal text width. For figures you could also extend it in the margin using the technique shown be me in Center figure that is wider than \textwidth and Place figures side by side, spill into outer margin.
In your case either use two box registers and then:
\makebox[1.2\textwidth]{\subfloat[Shorter code]{\usebox{\mylistingboxa}}\hfill\subfloat[Larger code]{\usebox{\mylistingboxb}}}
or add the following equivalent lines before and after the whole subfloat related code:
\hbox to 1.2\textwidth\bgroup\hss
% the whole box saving and \subfloat code above
\hss\egroup
Best Answer
Use
keepspaces=trueas part of your listing settings.