This will force WooCommerce sale items to the front of the store listing, prices lowest to highest, then sorted by title A-Z.

WooCommerce Sale Products up front

/**
 * Sale Products Up Front 
 */

add_action( 'woocommerce_product_query', 'cur_sale_products_up_front', 10, 2);
add_filter('posts_request', 'cur_modify_products_query', 10, 2);
add_filter('loop_start', 'cur_reorder_sale_items');

//Utility function
function cur_replace_text($startPoint, $endPoint, $newText, $source) {
    $regex = '#('.preg_quote($startPoint).')(.*)('.preg_quote($endPoint).')#si';
    preg_match( $regex, $source, $matches);
    $newText = $newText . $matches[2];
    return preg_replace($regex, '$1'.$newText.'$3', $source);
}

function cur_sale_products_up_front($q, $this) {

    if ( isset($_SESSION['orderby']) && $_SESSION['orderby'] == 'menu_order' ) :
        $q->set('meta_key', '_sale_price');
        $q->set('products_query', 'true');
    endif;
    return $q;
}


function cur_modify_products_query($request, $object){
    if ( ! empty( $object->query_vars['products_query'] ) &&  isset($_SESSION['orderby']) && $_SESSION['orderby'] == 'menu_order' ) :
        global $wpdb;
        $new_orderby = $wpdb->postmeta . '.meta_value+0 desc, ';
        $request = cur_replace_text('ORDER BY ', ' LIMIT', $new_orderby, $request);
    endif;
    return $request;
}

function cur_reorder_sale_items($query){

    if( ! empty( $query->posts ) && $query->query_vars['post_type'] == 'product' ) :

        $posts = &$query->posts; 
        foreach( $posts as $key => $post ) :
            $sale_price = get_post_meta($post->ID,'_sale_price', TRUE);
            if( !empty( $sale_price ) )
                $sale_products[$key] = $sale_price;
        endforeach;

        if( !empty ($sale_products ) ) :
            arsort( $sale_products);

            foreach( $sale_products as $key => $post ) :
                $sale_products[$key] = $posts[$key];
                unset( $posts[$key] );
                array_unshift( $posts, $sale_products[$key] );
            endforeach;
        endif;

    endif;
    return $query;
}