Wordpress - Pagination on a WP_query not showing navigation links

Please do not use showposts it got replaced by posts_per_page ages ago.

Personally I would add the arguments to the WP_Query like shown below, additionally pagination should work like shown below:

$paged = ( get_query_var( 'paged' ) ) ? get_query_var( 'paged' ) : 1;
$args = array(
    'posts_per_page' => 4,
    'paged'          => $paged,
);
$the_query = new WP_Query( $args );

global $wp_query;
// Put default query object in a temp variable
$tmp_query = $wp_query;
// Now wipe it out completely
$wp_query = null;
// Re-populate the global with our custom query
$wp_query = $the_query;

if ( $the_query->have_posts() ) : 
    while ( $the_query->have_posts() ) : $the_query->the_post();
        // loop code
    endwhile;

    previous_posts_link( '« Newer posts' );
    next_posts_link( 'Older posts »', $the_query->max_num_pages );
    wp_reset_postdata();

else :
    // no post found code 
endif;

// Restore original query object
$wp_query = null;
$wp_query = $tmp_query;

Which is the same as the Q&A How to fix pagination for custom loops? I linked you to by @ChipBennett.

Another note, if this in a page template working as static front page, you have to use the query variable page instead of paged:

$paged = ( get_query_var( 'page' ) ) ? get_query_var( 'page' ) : 1;

A good thing to do, get the posts_per_page value from wordpress. You can change this value in wordpress admin menu.

$page = ( get_query_var( 'paged' ) ) ? get_query_var( 'paged' ) : 1;
if(!$page)
    $page = ( get_query_var( 'page' ) ) ? get_query_var( 'page' ) : 1;

$posts_per_page = get_option( 'posts_per_page' );

$query = new WP_Query( array(
    'posts_per_page' => $posts_per_page,
    'paged'          => $page,
    'post_status'    => 'publish',
    'orderby'        => 'title',
    'order'          => 'ASC',
) );

while ( $query->have_posts() ) {
    $query->the_post();

    // Code for Output
}