According to my mother, an editor for National Geographic Magazine, the correct phrase is:

"All of a sudden. Believe it or not, the phrase is in Webster's Third
International Dictionary, meaning 'sooner than expected.'"